A priority queue is a queue in which we insert an element at the back (enqueue) and remove an element from the front (dequeue). The element with the highest priority shall be dequeued first.

Table of Content


Why use heap

Heap is a complete binary tree, A complete binary tree is a binary tree in which all levels are completely filled and all the nodes in the last level are as left as possible. Based on these characteristic, it can be represented as an array. Each node’s position in the tree is corresponding to the index in the array as following diagram.

priority queue with heap

The relationship between the nodes in the heap has following formulas:
parentPos = (pos-1)/2
left = 2*pos+1
right=2*pos+2

Meanwhile, heap should also meets this criteria: the parent’s key is larger than both children’s keys. The max value is stored in the root. If we read the value level by level from top to bottom, all elements are partially sorted. Based on this, we can use heap to implement priority queue.

Please note when we use max heap, the priority queue is a descending priority (ie the bigger the key, the higher the priority). If we want ascending priority, we can use min heap to implement.


Map of priority queue implementations

Part 1 – priority queue implementation with ordered array
Part 2 – priority queue implementation with unordered array

you are here


Part 3 – priority queue implementation with heap – iterative solution
Part 4 – priority queue implementation with heap – recursive solution


Enqueue

We declare three attributes: heap, length and maxSize. heap is an array. maxSize is the max length of the array. It is used to initialize the array. length is actual number of elements in the array. It starts from 0.

To enqueue, we put the new value at the end of the array. Then we move it up based on its value compared to its parent. If it’s value larger than its parent, it should be switched the position with its parent. We call this process bubble up or heap up. The time complexity is O(logn).

Java

Javascript

Python

Doodle

priority queue heap iterative


Dequeue

The dequeue operation is to remove the highest priority element, which is the first one in the array. When we remove the first element in the array, we move the last element to the first position to fill out the empty spot. But this element’s value might be smaller than it children. To correct this, we compare its value with its children’s values, and switch with the child with the larger value. This process is called bubble down or heap down. The time complexity is O(logn).

Java

Javascript

Python

Doodle

priority queue heap delete


Peek

Peek is to return the value of the highest priority element. Since the first one already has the largest value, this can be done by returning the first element in the array.

Java

Javascript

Python


Print

Print is to print all elements in the array, starting from the index 0 to highest index. A for loop is used to iterate through each element.

Java

Javascript

Python


Free download

Download priority queue using heap (iterative solution) in Java, JavaScript and Python
Download aggregate Data Structures implementations in Java
Download aggregate Data Structures implementations in JavaScript
Download aggregate Data Structures implementations in Python

What data structures do I use to implement priority queue?

pq with heap

You can use array and heap to implement priority queue. When using array, the time complexity of enqueue or dequeue is O(n) since it needs to find the biggest one. When using heap, the time complexity is O(logn). So heap is better.