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. This priority queue implementation provides code to implement a priority queue using a heap using recursion, in which the time complexity of enqueue is O(logn), and the space complexity is O(logn).

priority queue implementation

Check out why we use a heap to implement a priority queue.

Table of Content


Map of priority queue implementations

Part 1 – priority queue implementation with unordered array
Part 2 – priority queue implementation with ordered array
Part 3 – priority queue implementation with heap – iterative solution

you are here

Part 4 – priority queue implementation with heap – recursive solution


Enqueue

In the class, declare three attributes: heap, length, and maxSize. heap is an array to hold all elements in the priority queue. maxSize is the max size of the array. length is the actual number of elements in the array. It starts from 0.

To enqueue, you put the new value at the end of the array. Then you move it up based on its value compared to its parent. If its value is larger than its parent, it should be swapped 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 from the array. When you remove the first element in the array, you move the last element to fill out the empty spot. But this element’s value might be smaller than its children’s. To correct this, you 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.

Please note this implementation is using recursion. The time complexity is the same as iterative implementation O(logn). However, the space complexity has increased to O(logn) for the call stack. So it is not as efficient as the iterative approach.

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 the highest index. A for loop is used to iterate through each element.

Java

Javascript

Python


Free download

Download priority queue implementation using heap (recursive) in Java, JavaScript and Python
Data structures introduction PDF

What data structures are used to implement a priority queue?

An array or a heap can be used to implement a priority queue. When using an array, the time complexity of enqueue or dequeue is O(n). When using a heap, the time complexity is O(logn). So heap is better.