Normalization
November 30, 2023UGC NET CS 2018-DEC Paper-2
November 30, 2023Priority-Queue
|
Question 1
|
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?
When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?
|
Both Extract-Max(A) and Insert(A,key) run in O(1)
|
|
|
Both Extract-Max(A) and Insert(A,key) run in O(log(n))
|
|
|
Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(n)
|
|
|
Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(log(n))
|
Correct Answer: B