[Algo] 6.5 Priority queues

priority queue
A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key.


max-priority queue operations
INSERT(S, x)：insert the element x into the set S ($S \leftarrow S \cup \{x\}$)
MAXIMUM(S)：returns the element of S with the largest key
EXTRACT-MAX(S)：removes and returns the element of S with the largest key
INCREASE-KEY(S, x, k)：increases the value of element x's key to the new value k, which is assumed to be at least as large as x's current key value


max-priority implementation

@{
\proc{Heap-Maximum}(A)
\li \Return A[1]
}@

HEAP-MAXIMUM 可以實做 MAXIMUM，而且 running time 是 $\Theta(1)$

@{
\proc{Heap-Extract-Max}(A)
\li \If \;\textit{heap-size}[A] < 1
\li \;\;\;\;\textbf{error}\;\textup{"heap underflow"}
\li max = A[1]
\li A[1] = A[\textit{heap-size}[A]]
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li \proc{Max-Heapify}(A, 1)
\li \Return max
}@

HEAP-EXTRACT-MAX 可以實做 EXTRACT-MAX，running time 是 $O(\lg n)$

@{
\proc{Heap-Increase-Key}(A, i, key)
\li \If key < A[i]
\li \;\;\;\;\textbf{error}\;\textup{"new key is smaller than current key"}
\li A[i] = key
\li \While i > 1 \;\textup{and}\;A[\proc{Parent}(i)] < A[i]
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[\proc{Parent}(i)]
\li \;\;\;\;i = \proc{Parent}(i)
}@

HEAP-INCREASE-KEY 可以實做 INCREASE-KEY。因為 A[i] 的 value 被增加後可能會破壞掉原本 max-heap 的架構，所以我們應該重新再 heapify 一次，但是這邊採用比較簡單的作法，如果 A[i] 比 A[PARENT(i)] 還大的話，那我們就交換 A[i] 跟 A[PARENT(i)]，由下往上比對上去，所以最多只要比對到 root 而已，所以 running time 是 $O(\lg n)$。

@{
\proc{Max-Heap-Insert}(A, key)
\li \textit{heap-size}[A] = \textit{heap-size}[A] + 1
\li A[\textit{heap-size}[A]] = -\infty
\li \proc{Heap-Increase-Key}(A, \textit{heap-size}[A], key)
}@

MAX-HEAP-INSERT 可以實做 INSERT。running time 是 $O(\lg n)$。