欢迎光临
我的个人博客网站

使用C#实现数据结构堆

一、 堆的介绍:

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

  1. 堆中某个节点的值总是不大于或不小于其父节点的值

  任意节点的值小于(或大于)它的所有后裔,所以最小元(或最大元)在堆的根节点上(堆序性)。堆有大根堆和小根堆,将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

  2. 堆总是一棵完全二叉树

  除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。 

  堆示意图:

  使用C#实现数据结构堆

  将堆元素从上往下从左到右放进数组对象中,子父节点索引满足关系:

       parentIndex = (index+1)/ 2 – 1;

  childLeftIndex = parentIndex * 2 + 1;

  childRightIndex = (parentIndex + 1) * 2;

  其中:index为任一节点索引;parentIndex该节点父索引;childLeftIndex该父节点下的子左节点;childRightIndex该父节点下的子右节点。

  创建堆的大概思路: 

  1. 向堆中添加元素:

  加到数组尾处,循环比对其父节点值(大根堆和小根堆比对策略不一样),比对结果的目标索引不是父节点索引则交换子父节点元素,继续向上比对其父父节点…;直至比对过程中目标索引为父节点索引或达到根节点结束,新堆创建完成。

  2. 向堆中取出元素:

  取出根节点元素,并将堆末尾元素插入根节点(为了保证堆的完全二叉树特性),从根部再循环向下比对父节点、子左节点、子右节点值,比对结果目标索引不为父节点交换目标索引和父节点的值,向下继续比对;直至比对过程中目标索引为父节点索引或达到堆尾部结束,新堆创建完成。

二、 代码实现:

  因为大根堆和小根堆只是比较策略不同,所以整合了两者,用的时候可以直接设置堆的类别;默认小根堆,默认比较器。实现代码如下:

使用C#实现数据结构堆使用C#实现数据结构堆

  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类中小根堆先按年龄小者排序,年龄相同者按身高大者排序;而使用大根堆则相反。两种比较器写法,前者直接使用默认比较器;后者需要将比较器注入到堆中。

使用C#实现数据结构堆使用C#实现数据结构堆

 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

  主函数调用:

使用C#实现数据结构堆使用C#实现数据结构堆

 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

  输出结果:

  使用C#实现数据结构堆

  

  

  参考:

  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

 

 

赞(0) 打赏
未经允许不得转载:张拓的天空 » 使用C#实现数据结构堆
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏