No Book

Question

Which of the following data structure is efficient to implement priority queue with basic operation such as insertion, deletion and searching?

A) Linked list

B) Sorted array

C) Heap

D) Hash table

Comments

heap

Answer 1

Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked list. In a Binary Heap, getHighestPriority() can be implemented in O(1) time, insert() can be implemented in O(Logn) time and deleteHighestPriority() can also be implemented in O(Logn) time.

Comments

What about Hash? it has

Search: O(1)

Insert: O(1)

Delete: O(1)

---

In priority queue an element with highest priority is dequeued first. If same priority observed, they are served according to the order.

Now in case of hashing:

Average case scenerio is O(1).

But For chaining worst case is O(n). In case of linear probing same complexity O(n) persist in case of worst case.