[Algo] Exercise 6.5

Exercise 6.5-3
Write pseudocode for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap.

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

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

@{
\proc{Heap-Decrease-Key}(A, i, key)
\li \If key > A[i]
\li \;\;\;\;\textbf{error}\;\textup{"new key is larger 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)
}@

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

Exercise 6.5-4
Why do we bother setting the key of the inserted node to $-\infty$ in line 2 of MAX-HEAP-INSERT when the next thing we do is increase its key to the desired value?
To make sure that the inserted value is at least as large as current key value.


Exercise 6.5-6
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.
FIFO queue：when an element is inserted, it is given a value according to the inserting order. The later the element is inserted, the larger the value is given. Then we can implement a FIFO queue with a min-priority queue.
stack：Just like FIFO queue, when an element is inserted, it is given a value according to the inserting order. Then we can implement a stack with a max-priority queue.


Exercise 6.5-7
The operation HEAP-DELETE(A, i) deletes the item in node i from heap A. Give an implementation of HEAP-DELETE that runs in $O(\lg n)$ time for an n-element max-heap.
We assume that index i is never out of array boundary. The idea is we copy the value of A[heap-size[A]] to the deleted node A[i]. It may violate the heap priority, so we adopt the idea of HEAP-INCREASE-KEY. Otherwise, we call MAX-HEAPIFY to make the heap-priority hold.

@{
\proc{Heap-Delete}(A, i)
\li A[i] = A[\textit{heap-size}[A]]
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li key = A[i]
\li \If key < A[\proc{Parent}(i)]
\li \;\;\;\;\proc{Max-Heapify}(A, i)
\li \Else
\li \;\;\;\;\While i > 1 \;\textup{and}\; A[\proc{Parent}(i)] < key
\li \;\;\;\;\;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[\proc{Parent}(i)]
\li \;\;\;\;\;\;\;\;i = \proc{Parent}(i)
}@

Exercise 6.5-8
Give an $O(n \lg k)$-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. (Hint: Use a min-heap for k-way merging.)
We extract the 1st element from all k sorted lists to build a k-element heap. Then we call EXTRACT-MIN to obtain the smallest element, and extract the 2nd element from the list where the smallest element came from into the heap. After inserting a new element into the heap, we call MIN-HEAPIFY to make the min-heap priority hold. Continuing the process can yield a sorted list. The running time is clearly $nO(\lg k) = O(n \lg k)$.