The GATE Grind

GATE 2023 CS – Question 46

Programming and Data Structures · Binary Heaps · 2 marks · Multiple choice

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?

  1. Both Extract-Max(A) and Insert(A,key) run in O(1).
  2. Both Extract-Max(A) and Insert(A,key) run in O(log(n)).
  3. Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(n).
  4. Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(log(n)).

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 removes the root and then runs heapify (sift-down), which costs O(log n). Insert sifts up along one root-leaf path, which also costs O(log n).