# Cormen Edition 3 Exercise 6.5 Question 4 (Page No. 165)

59 views

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?

## Related questions

1
15 views
Write pseudo code 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.
HEAP-INCREASE-KEY(A,i,key) 1 if key < A[i] 2 error new key is smaller than current key 3 A[i] = key 4 while i > 1 and A[parent(i)] < A[i] 5 exchange A[i] with A[parent(i)] 6 i=parent(i) MAX-HEAP-INSERT(A,key) 1 A.heapsize = A.heapsize + 1 2 A[A.heapsize] ... -KEY(A,A.heapsize,key) Illustrate the operation of MAX-HEAP-INSERT$(A,10)$ on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.
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 minheap for $k$-way merging.)