CLRS Solutions | Exercise 6.5-3

Write pseudocode for the procedures $\textsc{Heap-Minimum}$, $\textsc{Heap-Extract-Min}$, $\textsc{Heap-Decrease-Key}$, and $\textsc{Min-Heap-Insert}$ that implement a min-priority queue with a min-heap.

A min-priority queue is the mirror image of a max-priority queue. Instead of maintaining the largest element at the root, we maintain the smallest. This is useful for applications like event-driven simulation (where we process events in chronological order) or Dijkstra’s shortest-path algorithm.

The key insight is that min-priority queue operations are analogous to max-priority queue operations, with all comparisons reversed. Where max-heaps use “greater than” comparisons, min-heaps use “less than” comparisons.

Heap-Minimum

$$\textsc{Heap-Minimum}$$$$\begin{aligned} 1& \quad \textsc{Heap-Minimum}(A) \\ 2& \quad \textbf{return }\,A[1] \\ \end{aligned}$$

The $\textsc{Heap-Minimum}$ procedure simply returns the root element, which is the minimum in a min-heap. This takes $\Theta(1)$ time.

Heap-Extract-Minimum

$$\textsc{Heap-Extract-Min}$$$$\begin{aligned} 1& \quad \textsc{Heap-Extract-Min}(A) \\ 2& \quad \textbf{if }\,A.heap\text{-}size\,<\,1 \\ 3& \quad \qquad \textbf{error }\text{\textquotedblleft heap underflow\textquotedblright} \\ 4& \quad min\,=\,A[1] \\ 5& \quad A[1]\,=\,A[A.heap\text{-}size] \\ 6& \quad A.heap\text{-}size\,=\,A.heap\text{-}size\,-\,1 \\ 7& \quad \textsc{Min-Heapify}(A, \, 1) \\ 8& \quad \textbf{return }\,min \\ \end{aligned}$$

The $\textsc{Heap-Extract-Min}$ procedure removes and returns the minimum element. It replaces the root with the last element, decreases the heap size, and calls $\textsc{Min-Heapify}$ to restore the min-heap property. The running time is $O(\lg n)$ due to the $\textsc{Min-Heapify}$ call.

Heap-Decrease-Key

$$\textsc{Heap-Decrease-Key}(A, i, key)$$$$\begin{aligned} 1& \quad \textbf{if }\,key\,>\,A[i] \\ 2& \quad \qquad \textbf{error }\text{\textquotedblleft new key is larger than current key\textquotedblright} \\ 3& \quad A[i]\,=\,key \\ 4& \quad \textbf{while }\,i\,>\,1\textbf{ and }\,A[\textsc{Parent}(i)]\,>\,A[i] \\ 5& \quad \qquad \text{exchange}\,A[i]\,\text{with}\,A[\textsc{Parent}(i)] \\ 6& \quad \qquad i\,=\,\textsc{Parent}(i) \\ \end{aligned}$$

The $\textsc{Heap-Decrease-Key}$ procedure decreases the key of element $A[i]$ to the new value. After setting the new key, it bubbles the element up toward the root by repeatedly swapping with its parent whenever the parent is larger (violating the min-heap property). The running time is $O(\lg n)$ since the path to the root has length at most the height of the tree.

Min-Heap-Insert

$$\textsc{Min-Heap-Insert}$$$$\begin{aligned} 1& \quad A.heap\text{-}size\,=\,A.heap\text{-}size\,+\,1 \\ 2& \quad A[A.heap\text{-}size]\,=\,\infty \\ 3& \quad \textsc{Heap-Decrease-Key}(A, \, A.heap\text{-}size, \, key) \\ \end{aligned}$$

The $\textsc{Min-Heap-Insert}$ procedure adds a new element to the min-heap. It first expands the heap and inserts a sentinel value $\infty$ (larger than any actual key) at the new position. Then it calls $\textsc{Heap-Decrease-Key}$ to decrease this value to the desired key, which bubbles the new element to its correct position. The running time is $O(\lg n)$.