Heap vs Priority Queues vs Queues

Anmol Sehgal
2 min readJan 12, 2019

--

You must have come across these data structures- Heap/Queues/Priority Queues. Why do we need Priority Queues when we have Queues. And also heaps are referred to as priority queues, then are they same? What's the difference between queues/Priority Queues and Heaps/Priority Queues? Let's discuss these.

Queues:

These are very easy to understand. Like the queues in real, the first entry into the queue is the first one to be taken out i.e. FIFO- first In first Out.
e.g. if we entered these numbers in the following order: 6 → 3 → 8 → 2 into the queue. Then while popping the values from it: the order of their pop will be: 6 → 3 → 8 → 2, i.e. the same order as of insertion. 6 was entered first, so it will be taken out before the rest.

Priority Queue:

As the name suggests, it is a queue but has something to do with priority.
While taking out the values from PQ, the entry with the highest priority is removed first(not following the FIFO order as in normal Queues).
Take, for example, the insertion order:
A(P= 4) → B(P=3)→ C(P=5) → D(p=9)

So while taking out from PQ, the removal order will be:
D(p=9) → C(P=5) → A(P= 4) → B(P=3)

So in a way, it is not strictly a Queue, but I guess the name Priority Queue is used because if more than 1 elements have the same priority, then their order or removal is by FIFO manner. So it has queue properties as well.

Heaps:

Heap is the data structure best suited to implement Priority Queues. Heaps are represented using arrays(usually) and can get maximum(or highest priority) element in O(1).
The Heaps are visualized as a binary tree, with elements stored internally in an array, as shown:

So the element with the highest priority is always the root, which makes the getMax() operation of O(1).

--

--

Responses (1)