Computer Sciences > GATE 2023 > Data Structures
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)).

Correct : b

Similar Questions

Consider a sequence a of elements a0 = 1, a1 = 5, a2 = 7, a3 = 8, a4 = 9, and a5 = 2. The following operations are performed on a stack S and a queue Q, both of...
#994 Fill in the Blanks
Consider a sequence a of elements a0 = 1, a1 = 5, a2 = 7, a3 = 8, a4 = 9, and a5 = 2. The following operations are performed on a stack S and a queue Q, both of...
#994 Fill in the Blanks
Consider a sequence a of elements a0 = 1, a1 = 5, a2 = 7, a3 = 8, a4 = 9, and a5 = 2. The following operations are performed on a stack S and a queue Q, both of...
#994 Fill in the Blanks

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......
Question Options

Contributed by: