如何基于最大堆实现最大优先队列

1. 优先队列

优先队列(priority queue)是一种用来维护由一组元素构成的集合A的数据结构, 其中的每个元素(x$x$)都有一个相关的值, 称为关键字(key$key$).

一个最大优先队列支持以下操作:

• MaxHeapInsert(A$A$, key$key$): 将元素x$x$插入到集合A$A$中
• HeapMaximum(A$A$): 返回A$A$中具有最大关键字的元素
• HeapExtractMax(A$A$): 去掉并返回A$A$中具有最大关键字的元素
• HeapIncreaseKey(A$A$, x$x$, k$k$): 将元素x$x$的关键字值增加到k$k$, 这里假设k$k$的值不小于x$x$的原关键字值.

在包含n个元素的堆中, 所有优先队列的操作都可以在O$O$(lgn$n$)事件内完成.

2. 过程分解

2.1 插入元素

MaxHeapInsert的输入是要被插入到最大堆A中的元素的关键字. 可以先通过增加一个key值为负无穷的叶子结点来扩展最大堆, 同时调用HeapIncreaseKey来为新结点设置相对应的关键字, 同时保持最大堆的性质.

伪代码实现为:

MAX-HEAP-INSERT(A, key)
    A[heap-size] = A[heap-size] + 1
    A[A.heap-size] = -∞
    HEAP-INCREASE-KEY(A, A.heap-size, key)

2.2 获得最大关键字元素

HeapMaximum即返回堆中的最大值A[1]

伪代码实现为:

HEAP-MAXIMUM(A)
    return A[1]

2.3 取出最大关键字元素

HeapExtractMax即返回并除去堆中的最大值A[1], 再调用MaxHeapify来维护最大堆

伪代码实现为:

HEAP-EXTRACT-MAX(A)
    if A.heap-size < 1
    error "heap underflow"
    max = A[1]
    A[1] = A[heap-size]
    A.heap-size = A.heap-size - 1
    MAX-HEAPIFY(A, 1)
    return max

2.4 增大元素的关键字值

HeapIncreaseKey可以采用自底向上的方法, 当前元素关键字与其父结点关键字进行比较, 如果当前结点关键字比较大, 则与父结点进行交换; 不断循环该过程, 直至当前结点没有父结点., 或者当前结点关键字小于其父结点.

过程图解为:

伪代码实现为:

HEAP-INCREASE-KEY(A, i, key)
    if key < A[i]
        error "new key is smaller than current key"
    A[i] = key
    while i > 1 and A[PARENT(i)] < A[i]
        exchange A[i] with A[PARENT(i)]
        i = PARENT(i)