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).
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
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | //Descending priority, the higher the value, the higher the priority public class PriorityQueueHeapRecursive<T extends Comparable<T>> { T[] heap; int length; int maxSize; //Constructor, Time O(1) Space O(1) @SuppressWarnings("unchecked") public PriorityQueueHeapRecursive(int capacity) { maxSize = capacity; length = 0; heap = (T[]) new Comparable[maxSize]; } //Insert a new value in max heap, Time O(logn), Space O(1), n is number of items in heap public void enqueue(T value) { if (length == maxSize) { System.out.println("priority queue is full, cannot enqueue " + value); return; } heap[length] = value; heapUp(length); length++; } //Time O(logn), Space O(1), use swap private void heapUp(int pos) { while (heap[pos].compareTo(heap[(pos-1)/2]) > 0) { swap(pos, (pos-1)/2); pos = (pos-1)/2; } } //Time O(1) Space O(1) private void swap(int p1, int p2) { T tmp = heap[p1]; heap[p1] = heap[p2]; heap[p2] = tmp; } |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | //Descending priority, the higher the key, the higher the priority class PriorityQueueHeapRecursive { //Constructor, Time O(1) Space O(1) constructor(capacity) { this.maxSize = capacity; this.length = 0; this.heap = []; } //Insert a new value in max heap, Time O(logn), Space O(1), n is number of items in heap enqueue(value) { if (this.length == this.maxSize) { console.log("priority queue is full, cannot enqueue " + value); return; } this.heap[this.length] = value; this.heapUp(this.length); this.length++; } //Time O(logn), Space O(1), use swap heapUp(pos) { while (this.heap[pos] > this.heap[Math.floor((pos-1)/2)]) { this.swap(pos, Math.floor((pos-1)/2)); pos = Math.floor((pos-1)/2); } } //Time O(1) Space O(1) swap (p1, p2) { var tmp = this.heap[p1]; this.heap[p1] = this.heap[p2]; this.heap[p2] = tmp; } } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | # Descending priority, the higher the value, the higher the priority class PriorityQueueHeapRecursive: # Time O(1) Space O(1) def __init__(self, capacity): self.maxSize = capacity self.length = 0 self.heap = [None]*capacity #Insert a new value in max heap, Time O(logn), Space O(1), n is number of items in heap def enqueue(self, value): if self.length >= self.maxSize: print("reach max size, return") return self.heap[self.length] = value # put at last first self.heapUp(self.length) self.length += 1 # Time O(logn), Space O(1), use swap def heapUp(self, pos): while self.heap[pos] > self.heap[int((pos-1)/2)]: self.swap(pos, int((pos-1)/2)) pos = int((pos-1)/2) # Time O(1) Space O(1) def swap (self, p1, p2) : tmp = self.heap[p1] self.heap[p1] = self.heap[p2] self.heap[p2] = tmp |
Doodle
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | //Remove from max (first one), Time O(logn), Space O(h), call recursion public T dequeue() { if (length == 0) { System.out.println("queue is empty"); return null; } T max = heap[0]; heap[0] = heap[length-1]; //last put at first length--; heapDown(0); return max; } //Use recursion, Time O(logn), Space O(logn) private void heapDown(int pos) { if (pos >= (length / 2) && pos <= length) //reach leaf return; if (heap[pos].compareTo(heap[2*pos+1]) < 0 || heap[pos].compareTo(heap[2*pos+2]) < 0) { if (heap[2*pos+1].compareTo(heap[2*pos+2]) >0) { swap(pos, 2*pos+1); heapDown(2*pos+1); } else { swap(pos, 2*pos+2); heapDown(2*pos+2); } } } |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | //Remove from max (first one), Time O(logn), Space O(logn), call recursion dequeue() { if (this.length == 0) { console.log("queue is empty"); return null; } var max = this.heap[0]; this.heap[0] = this.heap[this.length-1]; //put last at first this.length--; this.heapDown(0); return max; } //Recursion, Time O(logn), Space O(logn) heapDown(pos) { if (pos >= Math.floor(this.length/2) && pos <= this.length) //reach leaf return; if (this.heap[pos] < this.heap[2*pos+1] || this.heap[pos] < this.heap[2*pos+2]) { if (this.heap[2*pos+1] > this.heap[2*pos+2]) { this.swap(pos, 2*pos+1); this.heapDown(2*pos+1); } else { this.swap(pos, 2*pos+2); this.heapDown(2*pos+2); } } } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | # Remove from max (first one), Time O(logn), Space O(logn), call recursion def dequeue(self): max = self.heap[0] self.heap[0] = self.heap[self.length-1] #put the last at first self.length -= 1 self.heapDown(0) return max # Use recursion, Time O(logn), Space O(logn) def heapDown(self, pos): if pos >= int(self.length/2) and pos <= self.length: #reach leaf return if self.heap[pos] < self.heap[2*pos+1] or self.heap[pos] < self.heap[2*pos+2]: if self.heap[2*pos+1] > self.heap[2*pos+2]: self.swap(pos, 2*pos+1) self.heapDown(2*pos+1) else: self.swap(pos, 2*pos+2) self.heapDown(2*pos+2) |
Doodle
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
1 2 3 4 5 6 7 8 | //Time O(1) Space O(1) public T peek() { if (length == 0) { System.out.println("queue is empty"); return null; } return heap[0]; } |
Javascript
1 2 3 4 5 6 7 8 | //Time O(1) Space O(1) peek() { if (this.length == 0) { console.log("queue is empty"); return null; } return this.heap[0]; } |
Python
1 2 3 4 5 6 | # Time O(1) Space O(1) def peek(self): if self.length == 0: print("queue is empty") return None return self.heap[0] |
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
1 2 3 4 5 6 | //Print as array, Time O(n), Space O(1) public void print() { for (int i = 0; i < length; i++) System.out.print(heap[i] + " "); System.out.println(); } |
Javascript
1 2 3 4 5 6 7 8 | //Print as array, Time O(n), Space O(n) print() { var s = ""; for(let i = 0; i < this.length; i++) { s += this.heap[i] + " " ; } console.log(s); } |
Python
1 2 3 4 5 | # Print as array, Time O(n), Space O(1) def print(self): for i in range( 0, self.length, +1): print(self.heap[i], end = ' ') print() |
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.