优先队列

本文最后更新于：2024年8月18日上午

阅前警告

本文内容可能高度抽象，仅作为笔记参考

什么事优先队列

一种以一定顺序（根据优先值）组织起各个数据的数据结构，支持（高效地）删除最大（或最小）元素、插入元素两种基本操作。
我们经常通过（二叉）堆来实现优先队列。二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使用数组的第一个位置）。堆有序：当一棵二叉树的每个结点都大于等于（小于等于也成立？）它的两个子结点时，它被称为堆有序。根结点是堆有序的二叉树中的最大结点。
在二叉堆中，位置为k的父结点的位置就是k/2，它的两个子结点的位置就是2k和2k+1。

优先队列的实现

上浮与下沉

堆的两个基本操作（插入元素和删除优先级最高元素）都会打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复。我们称这个过程为“堆的有序化(reheapifying)”。
堆的有序化有两种情况：上浮(swim)与下沉(sink)
上浮，即：在堆底加入一个新的元素时，需由下至上恢复堆的顺序。swim的实现如下：

private void Swim(int k)
{
    while (k > 1 && Less(k / 2, k))
    {  // 当前结点不为根结点，且父结点要更小
        Exch(k / 2, k);  // 交换当前结点与父结点的位置
        k = k / 2;  // 更新 k 值
    }
}

下沉，即：将根结点替换为一个较小的元素时，需由上至下恢复堆的顺序。sink的实现如下：

private void Sink(int k)
{
    while (2 * k <= n)
    {  // 当前结点存在子结点
        int j = 2 * k;  // 找到其（左）子结点的位置
        if (j < n && Less(j, j + 1))  // 找出两个子结点中更大的那个子结点
        {
            j++;  // 若执行到这，说明右子结点更大，否则左子结点更大
        };
        if (!Less(k, j))  // 如果当前结点比子结点大，说明已下沉至合适位置，less()返回 false，if 条件成立，退出循环
        {
            break;
        }
        Exch(k, j);  // 否则交换当前结点与子结点的位置
        k = j;  // 并更新 k 值
    }
}

插入与删除

插入：

public void Insert(Key x)
{
    if (n == pq.Length - 1)  // 如果数组已满，扩容
    {
        Resize(2 * pq.Length);
    }
    pq[++n] = x;
    Swim(n);  // 将新元素上浮到合适位置
    Debug.Assert(IsMaxHeap());
}

删除（优先级）最大元素：

public Key DelMax()
{
    if (IsEmpty())
    {
        throw new InvalidOperationException("Priority queue underflow.");
    }
    Key max = pq[1];
    Exch(1, n--);  // 交换最大元素和最后一个元素
    Sink(1);  // 将新的根节点下沉到合适位置
    pq[n + 1] = default(Key);  // 垃圾回收
    if ((n > 0) && (n == (pq.Length - 1) / 4))
    {
        Resize(pq.Length / 2);  // 如果数组大小为 1/4 时，缩小数组
    }
    Debug.Assert(IsMaxHeap());
    return max;
}