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. The Priority queue can be implemented with array or heap.

We have introduced why we use heap to implement priority queue.

Table of Content


Map of priority queue implementations

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

you are here

Part 4 – priority queue implementation with heap – recursive solution


Enqueue

First we 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 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 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 we remove the first element in the array, we 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, 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.

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 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 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
Download aggregate Data Structures implementations in Java
Download aggregate Data Structures implementations in JavaScript
Download aggregate Data Structures implementations in Python

What are the ways to implement priority queues using heap?

pq with heap

There are two ways to implement priority queue with heap. The first is to implement using iteration. The second is to use recursion. Their time complexities are the same O(logn). As far as space complexity, iteration is better since it doesn’t need extra space. Recursive solution needs extra space for recursion’s call stacks.