C#实现优先队列和堆排序

C#实现优先队列和堆排序攻略

什么是优先队列？

优先队列（Priority Queue）是在数据结构中使用频率很高的一种类型，它的主要特点是能够在数据插入时将数据进行优先级的排序。

并且每次取出数据时取的是优先级最高的数据。

通常情况下我们使用最大堆来实现优先队列。

最大堆是一种特殊的堆，它的特点是每个结点都大于等于它的子结点。

什么是堆排序？

堆排序是一种排序算法，它通过建立最大堆（或最小堆）来实现排序。排序的过程分两步：第一步是通过建立最大堆，将元素最大的元素交换到第一位（或最小堆元素交换到末位）。第二步是将其余无序元素继续建立最大堆，直到无序的元素只剩最后一个，排序完成。

实现优先队列和堆排序

1. 实现最大堆

最大堆可以用数组来实现。

数组下标从0开始，节点i的左儿子为2i+1，右儿子为2i+2，父节点为(i-1)/2。

class MaxHeap<T> where T : IComparable<T>
{
    private List<T> Heap;

    public MaxHeap()
    {
        Heap = new List<T>();
    }

    public void Insert(T item)
    {
        Heap.Add(item);
        int n = Heap.Count - 1;
        while (n != 0 && Heap[n].CompareTo(Heap[(n - 1) / 2]) > 0)
        {
            T temp = Heap[n];
            Heap[n] = Heap[(n - 1) / 2];
            Heap[(n - 1) / 2] = temp;
            n = (n - 1) / 2;
        }
    }

    public T RemoveMax()
    {
        int n = Heap.Count - 1;
        T max = Heap[0];
        Heap[0] = Heap[n];
        Heap.RemoveAt(n);
        n--;
        int i = 0, j = 1;
        while (j <= n)
        {
            if (j < n && Heap[j].CompareTo(Heap[j + 1]) < 0)
            {
                j++;
            }
            if (Heap[i].CompareTo(Heap[j]) < 0)
            {
                T temp = Heap[i];
                Heap[i] = Heap[j];
                Heap[j] = temp;
            }
            else
            {
                break;
            }
            i = j;
            j = i * 2 + 1;
        }
        return max;
    }
}

2. 实现优先队列

使用最大堆实现优先队列。

class PriorityQueue<T> where T : IComparable<T>
{
    private MaxHeap<T> Heap;

    public PriorityQueue()
    {
        Heap = new MaxHeap<T>();
    }

    public void Enqueue(T item)
    {
        Heap.Insert(item);
    }

    public T Dequeue()
    {
        return Heap.RemoveMax();
    }
}

3. 实现堆排序

使用前面实现的最大堆实现堆排序。

class HeapSort<T> where T : IComparable<T>
{
    private static void Heapify(List<T> list)
    {
        int n = list.Count - 1;
        int i = (n - 1) / 2;
        while (i >= 0)
        {
            int maxIndex = i;
            int j = i * 2 + 1;
            while (j < n)
            {
                if (j + 1 < n && list[j].CompareTo(list[j + 1]) < 0)
                {
                    j++;
                }
                if (list[maxIndex].CompareTo(list[j]) < 0)
                {
                    maxIndex = j;
                }
                j = j * 2 + 1;
            }
            if (maxIndex != i)
            {
                T temp = list[i];
                list[i] = list[maxIndex];
                list[maxIndex] = temp;
            }
            i--;
        }
    }

    public static List<T> Sort(List<T> list)
    {
        int n = list.Count - 1;
        int i = n;
        while (i > 0)
        {
            T temp = list[0];
            list[0] = list[i];
            list[i] = temp;
            i--;
            Heapify(list.GetRange(0, i + 1));
        }
        return list;
    }
}

4. 示例说明

示例1：使用优先队列实现数组中最小的k个数

public static List<int> GetLeastNumbers(int[] arr, int k)
{
    PriorityQueue<int> pq = new PriorityQueue<int>();
    foreach (int i in arr)
    {
        if (pq.GetCount() < k || i < pq.Peek())
        {
            pq.Enqueue(i);
        }
        if (pq.GetCount() > k)
        {
            pq.Dequeue();
        }
    }
    return pq.GetList();
}

示例2：使用堆排序对数组进行排序

List<int> list = new List<int>() {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
list = HeapSort<int>.Sort(list);
foreach (int i in list)
{
    Console.Write($"{i} ");
}

总结

通过本文的介绍，我们了解了优先队列和堆排序的原理，并通过C#完成了基本的实现。

需要注意的地方是在实现最大堆和堆排序时，数组下标和计算有些不同，需要结合代码仔细理解。除此之外，最大堆和堆排序还有其他更高效、更复杂的实现方式，读者可以自行查阅学习。