# Cormen Edition 3 Exercise 6.5 Question 1 (Page No. 164)

21 views
HEAP-EXTRACT-MAX(A)

1  if A.heap-size < 1
2  error “heap underflow”
3  max=A[1]
4  A[1]=A[A.heapsize]
5  A.heapsize=A.heapsize-1
6  MAX-HEAPIFY(A,1)
7  return max  

Illustrate the operation of HEAP-EXTRACT-MAX on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.

## Related questions

1
34 views
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.)
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.
Each exchange operation on line $5$ of HEAP-INCREASE-KEY typically requires three assignments. Show how to use the idea of the inner loop of INSERTION-SORT to reduce the three assignments down to just one assignment.