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 iteration, in which the time complexity of enqueue is O(logn), and the space complexity is O(1).

Table of Content


Why use a heap

A heap is a complete binary tree, which 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 this characteristic, it can be represented as an array. Each node’s position in the tree corresponds to the index in the array as following diagram.

priority queue implementation

You can get the parent or children’s indices by the current index:
parentIndex = (index-1) / 2
leftIndex = 2*index + 1
rightIndex=2*index + 2

Meanwhile, a heap should also meet this criterion: the parent’s value is larger than both children’s values. The max value is stored in the root. So a heap is partially sorted. Based on this, you can use a heap to implement a priority queue.

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


Map of priority queue implementations

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

you are here


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


Enqueue

In the class, 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 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 move it up based on its value compared to its parent. If its value is larger than its parent, it should be switched to 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 you remove the first element in the array, you move the last element to the first position to fill out the empty spot. But this element’s value might be smaller than its children. 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. 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 the 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
Data structures introduction PDF

What are the ways to implement a priority queue using a heap?

There are two ways to implement a priority queue with a heap: iteration and recursion. Their time complexities are the same O(logn). But recursion needs memory space for function calls’ call stacks, while iteration doesn’t. So iterative method is better.