GATEBOOK exam

Question

Suppose that an application have a huge number of insert operations, but only few delete max operations. Which priority-queue implementation would be most effective:

A) Max heap

B) unordered array

C) ordered array

D) Binary search tree

Comments

Unordered Array.

$O(1)$ -- Insertion

$O(n)$ -- Deletion

---

cant we do using maxheap using O(logn)  time?

---

extract_max() in max heap can be done in O(1) time but number of operations are very small.

And Insertion takes $O(log(n))$ time in maxi-heap whereas number of operations are large in number.

Read this. Hope it clears your doubt

---

Yes for few delete op, using max_heap is unreasonable.

Answer 1

There are four implementations for priority queue:

Structure	Insertion	Extract-max
Unordered list	$O(1)$	$O(n)$
Ordered list	$O(n)$	$O(1)$
Binary Search Tree	$O(log\;n)$	$O(log\;n)$
Heap	$O(log\;n)$	$O(log\;n)$

When there are large number of insertion operations, unordered list is preferable. 

Comments

I aggree

but for BST , insertion and extract max will take O(n) ryt? in worst case it will be left skewed or right skewed