快捷導(dǎo)航

使用C#實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)堆的代碼

更新時(shí)間：2021年02月05日 14:27:44 作者：JN-SHao

這篇文章主要介紹了使用C#實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)堆，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

一、堆的介紹：

　　堆是用來排序的，通常是一個(gè)可以被看做一棵樹的數(shù)組對象。堆滿足已下特性：

　　1. 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值

　　任意節(jié)點(diǎn)的值小于（或大于）它的所有后裔，所以最小元（或最大元）在堆的根節(jié)點(diǎn)上（堆序性）。堆有大根堆和小根堆，將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。

　　2. 堆總是一棵完全二叉樹

　　除了最底層，其他層的節(jié)點(diǎn)都被元素填滿，且最底層盡可能地從左到右填入。　

　　堆示意圖：

　　將堆元素從上往下從左到右放進(jìn)數(shù)組對象中，子父節(jié)點(diǎn)索引滿足關(guān)系：

　　parentIndex = （index+1）/ 2 - 1;

　　childLeftIndex = parentIndex * 2 + 1;

　　childRightIndex = (parentIndex + 1) * 2;

　　其中：index為任一節(jié)點(diǎn)索引；parentIndex該節(jié)點(diǎn)父索引；childLeftIndex該父節(jié)點(diǎn)下的子左節(jié)點(diǎn)；childRightIndex該父節(jié)點(diǎn)下的子右節(jié)點(diǎn)。

　　創(chuàng)建堆的大概思路：　

　　1. 向堆中添加元素：

　　加到數(shù)組尾處，循環(huán)比對其父節(jié)點(diǎn)值（大根堆和小根堆比對策略不一樣），比對結(jié)果的目標(biāo)索引不是父節(jié)點(diǎn)索引則交換子父節(jié)點(diǎn)元素，繼續(xù)向上比對其父父節(jié)點(diǎn)…；直至比對過程中目標(biāo)索引為父節(jié)點(diǎn)索引或達(dá)到根節(jié)點(diǎn)結(jié)束，新堆創(chuàng)建完成。

　　2. 向堆中取出元素：

　　取出根節(jié)點(diǎn)元素，并將堆末尾元素插入根節(jié)點(diǎn)（為了保證堆的完全二叉樹特性），從根部再循環(huán)向下比對父節(jié)點(diǎn)、子左節(jié)點(diǎn)、子右節(jié)點(diǎn)值，比對結(jié)果目標(biāo)索引不為父節(jié)點(diǎn)交換目標(biāo)索引和父節(jié)點(diǎn)的值，向下繼續(xù)比對；直至比對過程中目標(biāo)索引為父節(jié)點(diǎn)索引或達(dá)到堆尾部結(jié)束，新堆創(chuàng)建完成。

二、代碼實(shí)現(xiàn)：

　　因?yàn)榇蟾押托「阎皇潜容^策略不同，所以整合了兩者，用的時(shí)候可以直接設(shè)置堆的類別；默認(rèn)小根堆，默認(rèn)比較器。實(shí)現(xiàn)代碼如下：

public class Heap<T>
 {
  private T[] _array;//數(shù)組，存放堆數(shù)據(jù)
  private int _count;//堆數(shù)據(jù)數(shù)量
  private HeapType _typeName;//堆類型
  private const int _DefaultCapacity = 4;//默認(rèn)數(shù)組容量/最小容量
  private const int _ShrinkThreshold = 50;//收縮閾值（百分比）
  private const int _MinimumGrow = 4;//最小擴(kuò)容量
  private const int _GrowFactor = 200; // 數(shù)組擴(kuò)容百分比,默認(rèn)2倍
  private IComparer<T> _comparer;//比較器
  private Func<T, T, bool> _comparerFunc;//比較函數(shù)

  //堆數(shù)據(jù)數(shù)量
  public int Count => _count;
  //堆類型
  public HeapType TypeName => _typeName;


  public Heap() : this(_DefaultCapacity, HeapType.MinHeap, null) { }
  public Heap(int capacity) : this(capacity, HeapType.MinHeap, null) { }
  public Heap(HeapType heapType) : this(_DefaultCapacity, heapType, null) { }
  public Heap(int capacity, HeapType heapType, IComparer<T> comparer)
  {
   Init(capacity, heapType, comparer);
  }
  public Heap(IEnumerable<T> collection, HeapType heapType, IComparer<T> comparer)
  {
   if (collection == null)
    throw new IndexOutOfRangeException();
   Init(collection.Count(), heapType, comparer);
   using (IEnumerator<T> en = collection.GetEnumerator())//避免T在GC堆中有非托管資源，GC不能釋放，需手動
   {
    while (en.MoveNext())
     Enqueue(en.Current);
   }
  }
  private void Init(int capacity, HeapType heapType, IComparer<T> comparer)
  {
   if (capacity < 0)
    throw new IndexOutOfRangeException();
   _count = 0;
   _array = new T[capacity];
   _comparer = comparer ?? Comparer<T>.Default;
   _typeName = heapType;
   switch (heapType)
   {
    default:
    case HeapType.MinHeap:
     _comparerFunc = (T t1, T t2) => _comparer.Compare(t1, t2) > 0;//目標(biāo)對象t2小
     break;
    case HeapType.MaxHeap:
     _comparerFunc = (T t1, T t2) => _comparer.Compare(t1, t2) < 0;//目標(biāo)對象t2大
     break;
   }
  }

  public T Dequeue()
  {
   if (_count == 0)
    throw new InvalidOperationException();
   T result = _array[0];
   _array[0] = _array[--_count];
   _array[_count] = default(T);

   if (_array.Length > _DefaultCapacity && _count * 100 <= _array.Length * _ShrinkThreshold)//縮容
   {
    int newCapacity = Math.Max(_DefaultCapacity, (int)((long)_array.Length * (long)_ShrinkThreshold / 100));
    SetCapacity(newCapacity);
   }
   AdjustHeap(_array, 0, _count);
   return result;
  }
  public void Enqueue(T item)
  {
   if (_count >= _array.Length)//擴(kuò)容
   {
    int newCapacity = Math.Max(_array.Length+_MinimumGrow, (int)((long)_array.Length * (long)_GrowFactor / 100));
    SetCapacity(newCapacity);
   }

   _array[_count++] = item;
   int parentIndex;
   int targetIndex;
   int targetCount = _count;
   while (targetCount > 1)
   {
    parentIndex = targetCount / 2 - 1;
    targetIndex = targetCount - 1;
    if (!_comparerFunc.Invoke(_array[parentIndex], _array[targetIndex]))
     break;
    Swap(_array, parentIndex, targetIndex);
    targetCount = parentIndex + 1;
   }
  }
  private void AdjustHeap(T[] array, int parentIndex, int count)
  {
   if (_count < 2)
    return;
   int childLeftIndex = parentIndex * 2 + 1;
   int childRightIndex = (parentIndex + 1) * 2;

   int targetIndex = parentIndex;
   if (childLeftIndex < count && _comparerFunc.Invoke(array[parentIndex], array[childLeftIndex]))
    targetIndex = childLeftIndex;
   if (childRightIndex < count && _comparerFunc.Invoke(array[targetIndex], array[childRightIndex]))
    targetIndex = childRightIndex;
   if (targetIndex != parentIndex)
   {
    Swap(_array, parentIndex, targetIndex);
    AdjustHeap(_array, targetIndex, _count);
   }
  }

  private void SetCapacity(int capacity)
  {
   T[] newArray = new T[capacity];
   Array.Copy(_array, newArray, _count);
   _array = newArray;
  }

  private void Swap(T[] array, int index1, int index2)
  {
   T temp = array[index1];
   array[index1] = array[index2];
   array[index2] = temp;
  }

  public void Clear()
  {
   Array.Clear(_array, 0, _count);
   Init(_DefaultCapacity, HeapType.MinHeap, null);
  }
 }

 public enum HeapType { MinHeap, MaxHeap }

三、使用測試：　

　　建一個(gè)Person類用來測試，例子中Person比較規(guī)則是：先按年齡比較，年齡相同再按身高比較。具體比較大小是由選擇堆的類別進(jìn)行不同的排序規(guī)則：如Person類中小根堆先按年齡小者排序，年齡相同者按身高大者排序；而使用大根堆則相反。兩種比較器寫法，前者直接使用默認(rèn)比較器；后者需要將比較器注入到堆中。

public class Person : IComparable<Person>
 {
  public string name { get; set; }
  public int Age { get; set; }

  public int Height { get; set; }
  public override string ToString()
  {
   return $"我叫{name}，年齡{Age}，身高{Height}";
  }

  //小根堆：先排年齡小，年齡相同，按身高大的先排；大根堆相反
  public int CompareTo(Person other)
  {
   if (this.Age.CompareTo(other.Age) != 0)
    return this.Age.CompareTo(other.Age);
   else if (this.Height.CompareTo(other.Height) != 0)
    return ~this.Height.CompareTo(other.Height);
   else
    return 0;
  }
 }

 public class personComparer : IComparer<Person>
 {
  //大根堆：先排年齡大，年齡相同，按身高大的先排；小根堆相反
  public int Compare(Person x, Person y)
  {
   if (x.Age.CompareTo(y.Age) != 0)
    return x.Age.CompareTo(y.Age);
   else if (x.Height.CompareTo(y.Height) != 0)
    return x.Height.CompareTo(y.Height);
   else
    return 0;
  }
 }

　　主函數(shù)調(diào)用：

static void Main(string[] args)
  {
   int[] array = { 3, 5, 8, 3, 7, 1 };
   Heap<int> heap0 = new Heap<int>(array, HeapType.MaxHeap, null);
   Console.WriteLine(heap0.TypeName);
   Console.WriteLine(heap0.Dequeue());
   Console.WriteLine(heap0.Dequeue());
   Console.WriteLine(heap0.Dequeue());
   Console.WriteLine(heap0.Dequeue());
   int length = heap0.Count;
   for (int count = 0; count < length; count++)
   {
    Console.WriteLine(heap0.Dequeue());
   }

   Person person1 = new Person() { Age = 12, Height = 158, name = "張三" };
   Person person2 = new Person() { Age = 13, Height = 160, name = "李四" };
   Person person3 = new Person() { Age = 10, Height = 150, name = "王二" };
   Person person4 = new Person() { Age = 10, Height = 152, name = "麻子" };
   Person person5 = new Person() { Age = 12, Height = 150, name = "劉五" };
   List<Person> people = new List<Person>();
   people.Add(person1);
   people.Add(person2);
   people.Add(person3);
   people.Add(person4);
   people.Add(person5);
   Heap<Person> heap2 = new Heap<Person>(people, HeapType.MinHeap, null);
   Person person6 = new Person() { Age = 9, Height = 145, name = "趙六" };
   heap2.Enqueue(person6);
   Console.WriteLine(heap2.TypeName);
   Console.WriteLine(heap2.Dequeue());
   Console.WriteLine(heap2.Dequeue());
   Console.WriteLine(heap2.Dequeue());
   Console.WriteLine(heap2.Dequeue());

   PersonComparer personComparer = new PersonComparer();
   Heap<Person> heap3 = new Heap<Person>(1,HeapType.MaxHeap,personComparer);
   heap3.Enqueue(person1);
   heap3.Enqueue(person2);
   heap3.Enqueue(person3);
   heap3.Enqueue(person4);
   heap3.Enqueue(person5);
   heap3.Enqueue(person6);
   Console.WriteLine(heap3.TypeName);
   Console.WriteLine(heap3.Dequeue());
   Console.WriteLine(heap3.Dequeue());
   Console.WriteLine(heap3.Dequeue());
   Console.WriteLine(heap3.Dequeue());

   Console.ReadKey();
  }

　　輸出結(jié)果：

　　參考：

　　https://blog.csdn.net/qq826364410/article/details/79770791

　　https://docs.microsoft.com/zh-cn/dotnet/api/system.collections.generic.comparer-1?view=net-5.0

到此這篇關(guān)于使用C#實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)堆的代碼的文章就介紹到這了,更多相關(guān)C#實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)堆內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: