数据结构-05：优先级队列

基本概念

优先级队列是一种特殊的队列，其中每个元素都有一个优先级。出队时，优先级高的元素会先被处理。优先级队列可以用来实现任务调度、事件处理等。

普通队列按到达时间决定出队顺序，优先级队列则按关键字或优先级决定出队顺序。因此它不再是 FIFO 结构，而是“每次取当前最优元素”的结构。很多贪心算法都会用到优先级队列，例如 Dijkstra 每次取当前距离最小的顶点，Prim 每次取接入生成树代价最小的边或顶点。

优先级队列的简单实现：

方式一：入队时，按照优先级数值在队列（线性表）中寻找合适的位置，将新入队的元素插入在此位置。出队操作的实现保持不变。
方式二：入队时将新入队的元素直接放在队尾。但出队时，在整个队列中查找优先级最高的元素，让它出队。
时间复杂度分析：
- 方式一：入队操作的时间复杂度为 $O(n)$ ，出队操作的时间复杂度为 $O(1)$ 。
- 方式二：入队操作的时间复杂度为 $O(1)$ ，出队操作的时间复杂度为 $O(n)$ 。

二叉堆

二叉堆是一种特殊的完全二叉树，分为最大化堆 (大顶堆) 和最小化堆 (小顶堆) 满足堆的性质：对于每个节点，其值都大于或等于（或小于或等于）其子节点的值。

1
2
3

例如:序列 { 2,3,4,5,7,10,23,29,60 } 是最小化堆
序列 { 12,7,8,4,6,5,3,1} 是最大化堆
教材默认最小化堆

堆的两条性质要分开看：第一，它是完全二叉树，所以可以用数组按层序紧凑存储；第二，它满足堆序性质，小顶堆中父结点的关键字不大于孩子结点。若数组从 1 开始编号，则结点 i 的左孩子是 2i，右孩子是 2i + 1，父结点是 i / 2。这也是代码中 hole / 2、hole * 2 频繁出现的原因。

优先级队列的堆实现

使用二叉堆来实现优先级队列，入队和出队操作的时间复杂度均为 $O(\log n)$ 。

线性表的两种简单实现只能在入队和出队之间二选一：要么插入时维护有序，出队快；要么插入时不管顺序，出队再扫描。堆的折中更适合频繁交替的操作：它不要求整个数组有序，只要求父子之间满足堆序，因此每次修复只沿树高方向移动，代价是 $O(\log n)$ 。

类定义

template <class Type>
class priorityQueue:public queue<Type>
{
private:
    int currentSize; // 当前堆中元素个数
    Type *array;     // 用数组按层序存储完全二叉树
    int maxSize;     // 同顺序表定义
    void doubleSpace();
    void buildHeap( ); // 建堆
    void percolateDown( int hole ); // 从hole位置向下过滤
public:
    priorityQueue( int capacity = 100 ) {
        array = new Type[capacity];
        maxSize = capacity;
        currentSize = 0;
    }//顺序表初始化
    priorityQueue( const Type data[], int size );//建堆过程
    ~priorityQueue() { delete [] array; }
    bool isEmpty( ) const { return currentSize == 0; }
    void enQueue( const Type & x ); // 入队
    Type deQueue();
    Type getHead() { return array[1]; } // array[0]做了哨兵，堆顶在array[1]
};

小顶堆进队（向上过滤）

最坏情况（插入结点调整到顶）下一次完整调整过程的时间复杂度为 $O(\log n)$ ，因此入队操作的时间复杂度为 $O(\log n)$ 。

向上过滤的过程可以理解为“新元素先占住最后一个叶子位置，再一路向父结点比较”。如果新元素比父结点小，说明它应该更靠近堆顶，于是父结点下移，空洞 hole 上移。循环结束时，hole 就是新元素应该放入的位置。整个过程中并不是反复交换两个元素，而是一路移动父结点，最后一次性填入 x，这样写更高效。

template <class Type>
void priorityQueue<Type>::enQueue( const Type & x )
{
    if( currentSize == maxSize - 1 ) doubleSpace();
    // 向上过滤（调整）
    int hole = ++currentSize;
    for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 ) { //注意边界及下标的含义
        array[ hole ] = array[ hole / 2 ]; // 父结点下移，空位继续上浮
    }
    array[ hole ] = x; // 将新元素放到最终空位
}

小顶堆出队（向下过滤）

出队操作的时间复杂度为 $O(\log n)$ 。

出队时删除的是堆顶最小元素。为了保持完全二叉树的形状，代码把最后一个元素搬到根位置，然后执行向下过滤。向下过滤每一步都选择两个孩子中更小的那个上移，因为小顶堆要求父结点不大于任意孩子；如果当前保存的 tmp 已经不大于更小的孩子，堆序就恢复了，可以停止。

template <class Type>
Type priorityQueue<Type>::deQueue()
{
    Type minItem;
    minItem = array[ 1 ]; // 小顶堆堆顶即最小元素
    array[ 1 ] = array[ currentSize-- ]; // 用最后一个元素补到根位置
    percolateDown( 1 ); // 从根开始向下恢复堆序
    return minItem;
}

template <class Type>
void priorityQueue<Type>::percolateDown(int hole) {
    int child;                // 子节点索引
    Type tmp = array[hole];   // 保存当前节点的值

    // 循环直到当前节点没有子节点
    for (; hole * 2 <= currentSize; hole = child) {
        child = hole * 2;     // 左子节点

        // 如果右子节点存在且更小，则选择右子节点
        if (child != currentSize && array[child + 1] < array[child]) {
            child++;
        }

        // 如果子节点比当前节点小，则让更小的子节点上移
        if (array[child] < tmp) {
            array[hole] = array[child];
        } else {
            break;  // 否则终止循环
        }
    }

    // 将初始节点值放到最终位置
    array[hole] = tmp;
}

建堆

可以采取 $N$ 次连续插入的方式，但是，其时间复杂度 $O(N\log N)$ ，故不采纳。
实际上建堆的时间复杂度为 $O(N)$ ，可以通过从最后一个非叶子节点开始向下过滤的方式实现。

建堆从最后一个非叶子结点开始，是因为叶子结点天然已经满足堆序，不需要调整。自底向上处理时，每个子树在处理父结点之前都已经是堆，父结点只需做一次 percolateDown 就能把整棵子树修成堆。这种“先修小堆，再合成大堆”的顺序，是建堆能在线性时间完成的关键。

// percolateDown(int hole)部分
Type tmp = array[ hole ];
for( ; hole * 2 <= currentSize; hole = child ) {
    child = hole * 2; // 先定位左孩子
    if( child != currentSize && array[ child + 1 ] < array[ child ] ) child++;
    if( array[ child ] < tmp ) array[ hole ] = array[ child ];
    else break;
}
array[ hole ] = tmp;