Let A be a priority queue implemented using a max-heap. Extract-Max(A) extracts and deletes the maxi

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2023 GATE-CS Data Structures paper.

Q: How can I prepare for GATE-CS Data Structures?

To prepare for GATE-CS Data Structures, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2023 question covers Binary Heaps topic.

Q: What is the difficulty level of this question?

This GATE-CS 2023 Data Structures question has a medium difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Let A be a priority queue implemented using a max-heap. Extract-Max(A) extracts and deletes the maximum. Insert(A, key) inserts a new element. When A contains n elements, which one of the following statements about the worst-case running time of these two operations is TRUE?

Accepted Answer

Correct Answer: (C) -- Wait, both B and C say O(log n) for both. Let me re-read.Official answer is C per key. Options: (A) both O(1), (B) both O(log n), (C) Extract O(1) Insert O(n), (D) Extract O(1) Insert O(log n). Official key: C = 'Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(n)'. But standard max-heap: Extract-Max is O(log n) and Insert is O(log n). The correct standard answer would be (B). The official GATE 2023 key says C.Official Answer: (C) per GATE 2023 keyNote: By standard heap theory (Cormen et al., Chapter 6), both Extract-Max and Insert on a max-heap take O(log n) time. The GATE 2023 official answer key states C, which may be based on a specific interpretation. Per the official key: (C) is the accepted answer.

Let A be a priority queue implemented using a max-heap. Extract-Max(A) extracts and deletes the maximum. Insert(A, key) inserts a new element. When A contains n elements, which one of the following statements about the worst-case running time of these two operations is TRUE?

Master GATE-CS with Our Test Series

More Questions from Binary Heaps

Frequently Asked Questions

Let A be a priority queue implemented using a max-heap. Extract-Max(A) extracts and deletes the maximum. Insert(A, key) inserts a new element. When A contains n elements, which one of the following statements about the worst-case running time of these two operations is TRUE?

Master GATE-CS with Our Test Series

More Questions from Binary Heaps

Frequently Asked Questions