C#数据结构之最小堆的实现方法

什么是最小堆？

最小堆是一种特殊的二叉树结构，它满足以下两个条件：

1. 是一个完全二叉树。
2. 任意节点值不大于其子节点的值。

最小堆的根节点是整个堆中最小的元素，而它的左右子节点也必定是整个堆中数值最小的元素。

最小堆的实现

实现最小堆需要用到数组和指针，以下是一个简单的最小堆类。

public class MinHeap<T> where T : IComparable<T>
{
    private T[] _heap;
    private int _size = 0;
    private const int _defaultCapacity = 32;

    public MinHeap()
    {
        _heap = new T[_defaultCapacity];
    }

    public MinHeap(int capacity)
    {
        _heap = new T[capacity];
    }

    public void Insert(T item)
    {
        if (_size == _heap.Length)
        {
            Array.Resize(ref _heap, _heap.Length * 2);
        }

        _heap[_size] = item;
        ShiftUp(_size);
        _size++;
    }

    public T Pop()
    {
        if (_size == 0)
        {
            throw new InvalidOperationException("Heap is empty.");
        }

        var item = _heap[0];
        _size--;
        _heap[0] = _heap[_size];
        _heap[_size] = default(T);
        ShiftDown(0);
        return item;
    }

    private void ShiftUp(int i)
    {
        var parent = (i - 1) / 2;
        while (i > 0 && _heap[i].CompareTo(_heap[parent]) < 0)
        {
            var tmp = _heap[i];
            _heap[i] = _heap[parent];
            _heap[parent] = tmp;
            i = parent;
            parent = (i - 1) / 2;
        }
    }

    private void ShiftDown(int i)
    {
        var left = (i * 2) + 1;
        var right = (i * 2) + 2;
        var smallest = i;

        if (left < _size && _heap[left].CompareTo(_heap[smallest]) < 0)
        {
            smallest = left;
        }

        if (right < _size && _heap[right].CompareTo(_heap[smallest]) < 0)
        {
            smallest = right;
        }

        if (smallest != i)
        {
            var tmp = _heap[i];
            _heap[i] = _heap[smallest];
            _heap[smallest] = tmp;
            ShiftDown(smallest);
        }
    }
}

这个实现拥有两个构造函数，允许你选择初始容量。Insert 和 Pop 方法分别插入和删除元素。ShiftUp 和 ShiftDown 方法分别用于维护堆的性质。

之后，可以像下面这样使用这个类：

var heap = new MinHeap<int>();
heap.Insert(3);
heap.Insert(2);
heap.Insert(1);
Console.WriteLine(heap.Pop()); // 1
Console.WriteLine(heap.Pop()); // 2
Console.WriteLine(heap.Pop()); // 3

示例说明

假设有一个需要维护单一频率数据的应用，为了合理地利用内存占用和计算性能，在频率数据已经被加载到内存中的场景，可以使用最小堆进行排序查找，缩短算法时间。以下是实现场景的粗略思路：

1. 频率数组顺序扫描到数据，将数据一次加入最小堆；
2. 堆满后比较堆根节点，删除堆根数据，插入新数据；
3. 反复执行 2 步骤，最后得到排序完毕的数据，即为单一频率数据。

另一个实现场景可以是，在一个延迟加载的海量数据中，按指定大小分批序列化，存储到单独的文件，最后合并单独大小序列化文件成结果文件。在这个场景中，使用最小堆可以很好地将延迟加载的海量单一数据进行排序，便于分批序列化和合并文件操作，优化磁盘和时间性能。