一、 堆的介绍：
堆是用来排序的，通常是一个可以被看做一棵树的数组对象。堆满足已下特性：
1. 堆中某个节点的值总是不大于或不小于其父节点的值
任意节点的值小于（或大于）它的所有后裔，所以最小元（或最大元）在堆的根节点上（堆序性）。堆有大根堆和小根堆，将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
2. 堆总是一棵完全二叉树
除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。
堆示意图：
将堆元素从上往下从左到右放进数组对象中，子父节点索引满足关系：
parentindex = （index+1）/ 2 – 1;
childleftindex = parentindex * 2 + 1;
childrightindex = (parentindex + 1) * 2;
其中：index为任一节点索引；parentindex该节点父索引；childleftindex该父节点下的子左节点；childrightindex该父节点下的子右节点。
创建堆的大概思路：
1. 向堆中添加元素：
加到数组尾处，循环比对其父节点值（大根堆和小根堆比对策略不一样），比对结果的目标索引不是父节点索引则交换子父节点元素，继续向上比对其父父节点…；直至比对过程中目标索引为父节点索引或达到根节点结束，新堆创建完成。
2. 向堆中取出元素：
取出根节点元素，并将堆末尾元素插入根节点（为了保证堆的完全二叉树特性），从根部再循环向下比对父节点、子左节点、子右节点值，比对结果目标索引不为父节点交换目标索引和父节点的值，向下继续比对；直至比对过程中目标索引为父节点索引或达到堆尾部结束，新堆创建完成。
二、 代码实现：
因为大根堆和小根堆只是比较策略不同，所以整合了两者，用的时候可以直接设置堆的类别；默认小根堆，默认比较器。实现代码如下：
public class heap<t>
{
private t[] _array;//数组，存放堆数据
private int _count;//堆数据数量
private heaptype _typename;//堆类型
private const int _defaultcapacity = 4;//默认数组容量/最小容量
private const int _shrinkthreshold = 50;//收缩阈值（百分比）
private const int _minimumgrow = 4;//最小扩容量
private const int _growfactor = 200; // 数组扩容百分比,默认2倍
private icomparer<t> _comparer;//比较器
private func<t, t, bool> _comparerfunc;//比较函数
//堆数据数量
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;//目标对象t2小
break;
case heaptype.maxheap:
_comparerfunc = (t t1, t t2) => _comparer.compare(t1, t2) < 0;//目标对象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)//扩容
{
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 }
三、 使用测试：
建一个person类用来测试，例子中person比较规则是：先按年龄比较，年龄相同再按身高比较。具体比较大小是由选择堆的类别进行不同的排序规则：如person类中小根堆先按年龄小者排序，年龄相同者按身高大者排序；而使用大根堆则相反。两种比较器写法，前者直接使用默认比较器；后者需要将比较器注入到堆中。
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;
}
}
主函数调用：
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();
}
输出结果：
参考：
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
到此这篇关于使用c#实现数据结构堆的代码的文章就介绍到这了,更多相关c#实现数据结构堆内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！
黄山市民网：https://www.huangshanshimin.com/
