Priority queue implementation provides code to implement priority queue using an ordered array. 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.
Table of Content
Map of priority queue implementations
Part 1 – priority queue implementation – ordered array
Part 2 – priority queue implementation – unordered array
Part 3 – priority queue implementation with heap – iterative solution
Part 4 – priority queue implementation with heap – recursive solution
Enqueue
To enqueue an element in priority queue is the same as adding an element in a sorted array. If it is a descending priority (ie the bigger the key, the higher the priority), you can put the highest key at the end. If it is a ascending priority (ie the lower the key, the higher the priority), you put the lowest key at the end. In this implementation, we are applying descending priority.
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 |
//descending priority, the higher the key, the higher the priority @SuppressWarnings({"unchecked"}) public class PriorityQueueArray1<T extends Comparable<T>> { private int maxSize; private T[] pqArray; //use array to implement private int length = 0; //Constructor, Time O(1), Space O(1) public PriorityQueueArray1(int capacity) { this.maxSize = capacity; this.pqArray = (T[])new Comparable[capacity]; } //Add by moving the biggest at the end, Time O(n), Space O(1), n is priority queue length public void enqueue(T value) { if (length == maxSize) { System.out.println("priority queue is full, cannot enqueue " + value); return; } int i = length - 1; while (i >= 0 && value.compareTo(pqArray[i]) < 0) { //biggest put at the end pqArray[i+1] = pqArray[i]; i--; } pqArray[i+1] = value; length++; } } |
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 |
// Descending priority, the higher the key, the higher the priority class PriorityQueueArrayOrdered { //Constructor, Time O(1), Space O(1) constructor(capacity) { this.maxSize = capacity; this.pqArray = {}; this.length =0; } //Add by compare value, Time O(n), Space O(1), n is priority queue length enqueue(value) { if (this.length == this.maxSize) { console.log("priority queue is full, cannot enqueue " + value); return; } var i = this.length - 1; while (i >= 0 && value < this.pqArray[i]) { // biggest put at the end this.pqArray[i+1] = this.pqArray[i]; i--; } this.pqArray[i+1] = value; this.length++; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Descending priority, the higher the key, the higher the priority class PriorityQueueArrayOrdered: # Constructor, Time O(1), Space O(1) def __init__(self, capacity) : self.maxSize = capacity self.pqArray = {} self.length = 0 # Add by moving the biggest at the end, Time O(n), Space O(1), n is priority queue length def enqueue(self, value) : if (self.length == self.maxSize) : print("priority queue is full, cannot enqueue " + str(value)) return i = self.length - 1 while (i >= 0 and value < self.pqArray[i]) : # biggest put at the end self.pqArray[i+1] = self.pqArray[i] i -= 1 self.pqArray[i+1] = value self.length += 1 |
Doodle
Dequeue
The dequeue operation is to remove the highest priority element from the array. Since the array is already sorted, we can just remove the last element.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Remove from the end, Time O(1), Space O(1) public T dequeue() { if (isEmpty()) { System.out.println("queue is empty"); return null; } T item = pqArray[length - 1]; length --; return item; } //Check empty, Time O(1), Space O(1) public boolean isEmpty() { return length == 0; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Remove from the end, Time O(1), Space O(1) dequeue() { if (this.isEmpty()) { console.log("queue is empty"); return null; } var item = this.pqArray[this.length-1]; this.length --; return item; } //Check empty, Time O(1), Space O(1) isEmpty() { return this.length == 0; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 |
# Remove from the end, Time O(1), Space O(1) def dequeue(self) : if (self.isEmpty()) : print("queue is empty") return None item = self.pqArray[self.length-1] self.length -= 1 return item # Check empty, Time O(1), Space O(1) def isEmpty(self) : return self.length == 0 |
Peek
Peek is to return the value of the highest priority element. The same as dequeue, we simply return the value of the element at highest index.
Java
|
1 2 3 4 5 6 7 8 |
//Return the end value, Time O(1), Space O(1) public T peek() { if (isEmpty()) { System.out.println("queue is empty"); return null; } return pqArray[length-1]; } |
Javascript
|
1 2 3 4 5 6 7 8 |
//Return the end value, Time O(1), Space O(1) peek() { if (this.isEmpty()) { console.log("queue is empty"); return null; } return this.pqArray[this.length-1]; } |
Python
|
1 2 3 4 5 6 |
# Return the end value, Time O(1), Space O(1) def peek(self) : if (self.isEmpty()) : print("queue is empty") return None return self.pqArray[self.length-1] |
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
|
1 2 3 4 5 6 7 |
//print all, they are sorted, Time O(n), Space O(1) public void print() { System.out.print("Priority Queue: "); for (int i = 0; i < length; i++) System.out.print(pqArray[i] + " "); System.out.println(); } |
Javascript
|
1 2 3 4 5 6 7 |
//print all sorted, Time O(n), Space O(1) print() { var line = "Priority Queue: "; for (let i = 0; i < this.length; i++) line += this.pqArray[i] + " "; console.log(line); } |
Python
|
1 2 3 4 5 6 |
# print all, they are sorted, Time O(n), Space O(1) def print(self) : line = "Priority Queue: " for i in range (0, self.length): line += str(self.pqArray[i]) + " " print(line) |
Free download
Download priority queue implementation using ordered array in Java, JavaScript and Python
Data structures introduction PDF
What’s the difference between a sorted array and a priority queue?
A sorted array is fully sorted, in which all elements are in order. Priority queue is partially ordered, in which only the first element is either the biggest or the smallest. You can use a sorted array working as a priority queue, but it is not time efficient.