UGC NET CSE | June 2011 | Part 2 | Question: 25

Question

When the priority queue is represented by max heap, the insertion and deletion of an element can be performed in (queue containing $n$ elements)

• A. $\theta(n)$ and $\theta(1)$ respectively
• B. $\theta(n)$ and $\theta(n)$ respectively
• C. $\theta(1)$ and $\theta(1)$ respectively
• D. None of the above

Answer 1

D is answer

Inserting Element take O(logn ) in worst case.(insert at least then find its correct possition)

Deletion Element take O(logn ) in worst case.( 1st we have to search that element)

Answer 2

Ans: D
We can use heaps to implement the priority queue. It will take O(log N) time to insert and delete each element in the priority queue.
ref: https://www.hackerearth.com/practice/notes/heaps-and-priority-queues/