郑少群博客: 使用C#实现数据结构堆

一、堆的介绍：

　　堆是用来排序的，通常是一个可以被看做一棵树的数组对象。堆满足已下特性：

　　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    else20     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    else34     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   }57

View 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

原文转载：http://www.shaoqun.com/a/524573.html

跨境电商：https://www.ikjzd.com/

auditor：https://www.ikjzd.com/w/2437

智邦：https://www.ikjzd.com/w/2376

一、堆的介绍：　　堆是用来排序的，通常是一个可以被看做一棵树的数组对象。堆满足已下特性：　　1.堆中某个节点的值总是不大于或不小于其父节点的值　　任意节点的值小于（或大于）它的所有后裔，所以最小元（或最大元）在堆的根节点上（堆序性）。堆有大根堆和小根堆，将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。　　2.堆总是一棵完全二叉树　　除了最底层，其他层的节点都被元素填满，且最底
周宁：周宁
patpat：patpat
海牙认证：海牙认证
疫情恐慌过后，口红效应开始慢慢复苏？：疫情恐慌过后，口红效应开始慢慢复苏？
Shopee Q2订单飙升92.7%，印尼市场更超1.1亿单！：Shopee Q2订单飙升92.7%，印尼市场更超1.1亿单！

2021年2月3日星期三

使用C#实现数据结构堆