一、 堆的介紹：
堆是用來排序的，通常是一個可以被看做一棵樹的陣列物件，堆滿足已下特性：
1. 堆中某個節點的值總是不大于或不小于其父節點的值
任意節點的值小于（或大于）它的所有后裔，所以最小元（或最大元）在堆的根節點上（堆序性），堆有大根堆和小根堆，將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，
2. 堆總是一棵完全二叉樹
除了最底層，其他層的節點都被元素填滿，且最底層盡可能地從左到右填入，
堆示意圖：
將堆元素從上往下從左到右放進陣列物件中，子父節點索引滿足關系：
parentIndex = （index+1）/ 2 - 1;
childLeftIndex = parentIndex * 2 + 1;
childRightIndex = (parentIndex + 1) * 2;
其中：index為任一節點索引；parentIndex該節點父索引；childLeftIndex該父節點下的子左節點；childRightIndex該父節點下的子右節點，
創建堆的大概思路：
1. 向堆中添加元素：
加到陣列尾處，回圈比對其父節點值（大根堆和小根堆比對策略不一樣），比對結果的目標索引不是父節點索引則交換子父節點元素，繼續向上比對其父父節點…；直至比對程序中目標索引為父節點索引或達到根節點結束，新堆創建完成，
2. 向堆中取出元素：
取出根節點元素，并將堆末尾元素插入根節點（為了保證堆的完全二叉樹特性），從根部再回圈向下比對父節點、子左節點、子右節點值，比對結果目標索引不為父節點交換目標索引和父節點的值，向下繼續比對；直至比對程序中目標索引為父節點索引或達到堆尾部結束，新堆創建完成，
二、 代碼實作：
因為大根堆和小根堆只是比較策略不同，所以整合了兩者，用的時候可以直接設定堆的類別；默認小根堆，默認比較器，實作代碼如下：
1 public class Heap<T> 2 { 3 private T[] _array;//陣列，存放堆資料 4 private int _count;//堆資料數量 5 private HeapType _typeName;//堆型別 6 private const int _DefaultCapacity = 4;//默認陣列容量/最小容量 7 private const int _ShrinkThreshold = 50;//收縮閾值（百分比） 8 private const int _MinimumGrow = 4;//最小擴容量 9 private const int _GrowFactor = 200; // 陣列擴容百分比,默認2倍 10 private IComparer<T> _comparer;//比較器 11 private Func<T, T, bool> _comparerFunc;//比較函式 12 13 14 //堆資料數量 15 public int Count => _count; 16 //堆型別 17 public HeapType TypeName => _typeName; 18 19 20 public Heap() : this(_DefaultCapacity, HeapType.MinHeap, null) { } 21 public Heap(int capacity) : this(capacity, HeapType.MinHeap, null) { } 22 public Heap(HeapType heapType) : this(_DefaultCapacity, heapType, null) { } 23 public Heap(int capacity, HeapType heapType, IComparer<T> comparer) 24 { 25 Init(capacity, heapType, comparer); 26 } 27 public Heap(IEnumerable<T> collection, HeapType heapType, IComparer<T> comparer) 28 { 29 if (collection == null) 30 throw new IndexOutOfRangeException(); 31 Init(collection.Count(), heapType, comparer); 32 using (IEnumerator<T> en = collection.GetEnumerator())//避免T在GC堆中有非托管資源，GC不能釋放，需手動 33 { 34 while (en.MoveNext()) 35 Enqueue(en.Current); 36 } 37 } 38 private void Init(int capacity, HeapType heapType, IComparer<T> comparer) 39 { 40 if (capacity < 0) 41 throw new IndexOutOfRangeException(); 42 _count = 0; 43 _array = new T[capacity]; 44 _comparer = comparer ?? Comparer<T>.Default; 45 _typeName = heapType; 46 switch (heapType) 47 { 48 default: 49 case HeapType.MinHeap: 50 _comparerFunc = (T t1, T t2) => _comparer.Compare(t1, t2) > 0;//目標物件t2小 51 break; 52 case HeapType.MaxHeap: 53 _comparerFunc = (T t1, T t2) => _comparer.Compare(t1, t2) < 0;//目標物件t2大 54 break; 55 } 56 } 57 58 59 public T Dequeue() 60 { 61 if (_count == 0) 62 throw new InvalidOperationException(); 63 T result = _array[0]; 64 _array[0] = _array[--_count]; 65 _array[_count] = default(T); 66 67 if (_array.Length > _DefaultCapacity && _count * 100 <= _array.Length * _ShrinkThreshold)//縮容 68 { 69 int newCapacity = Math.Max(_DefaultCapacity, (int)((long)_array.Length * (long)_ShrinkThreshold / 100)); 70 SetCapacity(newCapacity); 71 } 72 AdjustHeap(_array, 0, _count); 73 return result; 74 } 75 public void Enqueue(T item) 76 { 77 if (_count >= _array.Length)//擴容 78 { 79 int newCapacity = Math.Max(_array.Length+_MinimumGrow, (int)((long)_array.Length * (long)_GrowFactor / 100)); 80 SetCapacity(newCapacity); 81 } 82 83 _array[_count++] = item; 84 int parentIndex; 85 int targetIndex; 86 int targetCount = _count; 87 while (targetCount > 1) 88 { 89 parentIndex = targetCount / 2 - 1; 90 targetIndex = targetCount - 1; 91 if (!_comparerFunc.Invoke(_array[parentIndex], _array[targetIndex])) 92 break; 93 Swap(_array, parentIndex, targetIndex); 94 targetCount = parentIndex + 1; 95 } 96 } 97 private void AdjustHeap(T[] array, int parentIndex, int count) 98 { 99 if (_count < 2) 100 return; 101 int childLeftIndex = parentIndex * 2 + 1; 102 int childRightIndex = (parentIndex + 1) * 2; 103 104 int targetIndex = parentIndex; 105 if (childLeftIndex < count && _comparerFunc.Invoke(array[parentIndex], array[childLeftIndex])) 106 targetIndex = childLeftIndex; 107 if (childRightIndex < count && _comparerFunc.Invoke(array[targetIndex], array[childRightIndex])) 108 targetIndex = childRightIndex; 109 if (targetIndex != parentIndex) 110 { 111 Swap(_array, parentIndex, targetIndex); 112 AdjustHeap(_array, targetIndex, _count); 113 } 114 } 115 116 private void SetCapacity(int capacity) 117 { 118 T[] newArray = new T[capacity]; 119 Array.Copy(_array, newArray, _count); 120 _array = newArray; 121 } 122 123 private void Swap(T[] array, int index1, int index2) 124 { 125 T temp = array[index1]; 126 array[index1] = array[index2]; 127 array[index2] = temp; 128 } 129 130 public void Clear() 131 { 132 Array.Clear(_array, 0, _count); 133 Init(_DefaultCapacity, HeapType.MinHeap, null); 134 } 135 } 136 137 public enum HeapType { MinHeap, MaxHeap }View Code
三、 使用測驗：
建一個Person類用來測驗，例子中Person比較規則是：先按年齡比較，年齡相同再按身高比較，具體比較大小是由選擇堆的類別進行不同的排序規則：如Person類中小根堆先按年齡小者排序，年齡相同者按身高大者排序；而使用大根堆則相反，兩種比較器寫法，前者直接使用默認比較器；后者需要將比較器注入到堆中，
1 public class Person : IComparable<Person> 2 { 3 public string name { get; set; } 4 public int Age { get; set; } 5 6 public int Height { get; set; } 7 public override string ToString() 8 { 9 return $"我叫{name}，年齡{Age}，身高{Height}"; 10 } 11 12 //小根堆：先排年齡小，年齡相同，按身高大的先排；大根堆相反 13 public int CompareTo(Person other) 14 { 15 if (this.Age.CompareTo(other.Age) != 0) 16 return this.Age.CompareTo(other.Age); 17 else if (this.Height.CompareTo(other.Height) != 0) 18 return ~this.Height.CompareTo(other.Height); 19 else 20 return 0; 21 } 22 } 23 24 public class personComparer : IComparer<Person> 25 { 26 //大根堆：先排年齡大，年齡相同，按身高大的先排；小根堆相反 27 public int Compare(Person x, Person y) 28 { 29 if (x.Age.CompareTo(y.Age) != 0) 30 return x.Age.CompareTo(y.Age); 31 else if (x.Height.CompareTo(y.Height) != 0) 32 return x.Height.CompareTo(y.Height); 33 else 34 return 0; 35 } 36 }View Code
主函式呼叫：
1 static void Main(string[] args) 2 { 3 int[] array = { 3, 5, 8, 3, 7, 1 }; 4 Heap<int> heap0 = new Heap<int>(array, HeapType.MaxHeap, null); 5 Console.WriteLine(heap0.TypeName); 6 Console.WriteLine(heap0.Dequeue()); 7 Console.WriteLine(heap0.Dequeue()); 8 Console.WriteLine(heap0.Dequeue()); 9 Console.WriteLine(heap0.Dequeue()); 10 int length = heap0.Count; 11 for (int count = 0; count < length; count++) 12 { 13 Console.WriteLine(heap0.Dequeue()); 14 } 15 16 17 18 Person person1 = new Person() { Age = 12, Height = 158, name = "張三" }; 19 Person person2 = new Person() { Age = 13, Height = 160, name = "李四" }; 20 Person person3 = new Person() { Age = 10, Height = 150, name = "王二" }; 21 Person person4 = new Person() { Age = 10, Height = 152, name = "麻子" }; 22 Person person5 = new Person() { Age = 12, Height = 150, name = "劉五" }; 23 List<Person> people = new List<Person>(); 24 people.Add(person1); 25 people.Add(person2); 26 people.Add(person3); 27 people.Add(person4); 28 people.Add(person5); 29 Heap<Person> heap2 = new Heap<Person>(people, HeapType.MinHeap, null); 30 Person person6 = new Person() { Age = 9, Height = 145, name = "趙六" }; 31 heap2.Enqueue(person6); 32 Console.WriteLine(heap2.TypeName); 33 Console.WriteLine(heap2.Dequeue()); 34 Console.WriteLine(heap2.Dequeue()); 35 Console.WriteLine(heap2.Dequeue()); 36 Console.WriteLine(heap2.Dequeue()); 37 38 39 PersonComparer personComparer = new PersonComparer(); 40 Heap<Person> heap3 = new Heap<Person>(1,HeapType.MaxHeap,personComparer); 41 heap3.Enqueue(person1); 42 heap3.Enqueue(person2); 43 heap3.Enqueue(person3); 44 heap3.Enqueue(person4); 45 heap3.Enqueue(person5); 46 heap3.Enqueue(person6); 47 Console.WriteLine(heap3.TypeName); 48 Console.WriteLine(heap3.Dequeue()); 49 Console.WriteLine(heap3.Dequeue()); 50 Console.WriteLine(heap3.Dequeue()); 51 Console.WriteLine(heap3.Dequeue()); 52 53 54 55 Console.ReadKey(); 56 } 57View Code
輸出結果：
參考：
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
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/256140.html
標籤：C#