Let A be a priority queue for maintaining a set of elements. Suppose A is…
2023
Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation Extract-Max(A) extracts and deletes the maximum element from A. The operation Insert(A,key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations.
When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?
- A.
Both Extract-Max(A) and Insert(A,key) run in O(1).
- B.
Both Extract-Max(A) and Insert(A,key) run in O(log(n)).
- C.
Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(n).
- D.
Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(log(n)).
Attempted by 156 students.
Show answer & explanation
Correct answer: B
Key idea: both operations may have to move an element along a path whose length is the heap height, which is O(log n).
Extract-Max(A): Remove the root (maximum), replace it with the last element, then restore the heap by heapify-down (swap with the larger child until the heap property holds). Each swap moves the element one level down, so the worst-case time is proportional to the heap height = O(log n).
Insert(A, key): Insert the new key at the next leaf position and then bubble it up (swap with parent while it is larger). In the worst case the element goes from a leaf to the root, which is O(heap height) = O(log n).
Conclusion: Both Extract-Max and Insert take worst-case time O(log n) when A is implemented as a max-heap.