GATE 2023 CS – Question 46
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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) Both Extract-Max(A) and Insert(A,key) run in O(log(n)).
Explanation
**Extract-Max.** Remove the root, move the last element to the root, then **sift down** (swap with the larger child) along one root-to-leaf path. The height of a heap is $\lfloor\log_2n\rfloor$, so this takes $O(\log n)$.
**Insert.** Place the new key at the end and **sift up** (swap with the parent while larger) along one root-to-leaf path: $O(\log n)$.
Neither can be done in $O(1)$ in the worst case. Both run in $O(\log n)$: option (B).