GATE CS 2023 (Forenoon) — Question 46

Data StructuresBinary Search Trees (BSTs) & Binary HeapsMCQ2 marks · −2/3 if wrongEasy

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. A
    Both Extract-Max(\( A \)) and Insert(\( A \), key) run in \( O(1) \).
  2. B
    Both Extract-Max(\( A \)) and Insert(\( A \), key) run in \( O(\log(n)) \).
  3. C
    Extract-Max(\( A \)) runs in \( O(1) \) whereas Insert(\( A \), key) runs in \( O(\log(n)) \).
  4. D
    Extract-Max(\( A \)) runs in \( O(1) \) whereas Insert(\( A \), key) runs in \( O(n) \).
Practise the full 2023-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Binary Search Trees (BSTs) & Binary HeapsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group