A priority queue is a queue in which we insert an element at the back (enqueue) and remove an element from the front (dequeue). In addition, every element has a priority associated with it. The element with the highest priority shall be dequeued first. The Priority queue can be implemented with array or heap.

We have introduced the mechanism why we use heap to implement priority queue. The implementation with iterative approach is given. In this post, we are using recursive approach.

Table of Content


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 heap up.

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 heap down.

Please note this implementation is using recursion. The time complexity is the same as iterative implementation O(h), h is the height of the heap. However, the space complexity has increased to O(h) 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

Download Java, JavaScript and Python code
Priority queue (part 1) – ordered array implementation
Priority queue (part 3) – heap iterative implementation
Heap animated visual
Data structures and Java collections