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 an unordered array, in which the time complexity of enqueue is O(1), and that of dequeue is O(n).
Table of Content
Map of priority queue implementations
Part 1 – priority queue implementation – unordered array
Part 2 – priority queue implementation – ordered array
Part 3 – priority queue implementation with heap – iterative solution
Part 4 – priority queue implementation with heap – recursive solution
Enqueue in priority queue implementation
To enqueue an element is the same as adding an element in a regular array -add the element at the next available spot in the array (ie at the end).
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | // Descending priority, the higher the value, the higher the priority @SuppressWarnings({"unchecked"}) public class PriorityQueueUnorderedArray<T extends Comparable<T>> { private T[] array; private int length; private int maxSize; public PriorityQueueUnorderedArray(int capacity) { maxSize = capacity; array = (T[])new Comparable[capacity]; } //Add at the end without sorting, Time O(1), Space O(1), public void enqueue(T value) { if (length == maxSize) { System.out.println("The priority queue is full! can not enqueue " + value); return; } array[length] = value; length++; } |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | //Descending priority, the higher the key, the higher the priority class PriorityQueueUnorderedArray { //Constructor, Time O(1), Space O(1) constructor(capacity) { this.maxSize = capacity; this.array = []; this.length = 0; } //Add at the end without sorting, Time O(1), Space O(1), enqueue(value) { if (this.length == this.maxSize) { console.log("priority queue is full, cannot enqueue " + value); return; } this.array[this.length] = value; this.length++; } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | # Descending priority, the higher the value, the higher the priority class PriorityQueueUnorderedArray: # Constructor, Time O(1), Space O(1) def __init__(self, capacity): self.maxSize = capacity self.array = [None]*capacity self.length = 0 # Add at the end without sorting, Time O(1), Space O(1) def enqueue(self, value): if (self.length == self.maxSize): print("priority queue is full, cannot enqueue " + str(value)) return self.array[self.length] = value self.length += 1 |
Doodle
Dequeue
The dequeue operation is to remove the highest priority element from the array. Since the array is not ordered, you have to find the highest priority element first. This requires to examine all elements in the array. Then move the last element in the array to this spot to replace (remove) it. This time complexity is O(n).
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | //Find the biggest and delete it, Time O(n), Space O(1) public T dequeue() { if (length == 0) { System.out.println("The priority queue is empty! can not dequeue."); return null; } int maxIndex = 0; for (int i = 1; i < length; i++) { //search for biggest if (array[i].compareTo (array[maxIndex]) > 0) { maxIndex = i; } } T item = array[maxIndex]; System.out.println("dequeue: " + item); length--; array[maxIndex] = array[length]; //move the last to this spot return item; } |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | //Find the biggest and delete it, Time O(n), Space O(1) dequeue() { if (this.length == 0) { console.log("queue is empty"); return null; } var maxIndex = 0; for (let i = 1; i < this.length; i++) { //search for biggest if (this.array[i] > this.array[maxIndex]) { maxIndex = i; } } var item = this.array[maxIndex]; this.length--; this.array[maxIndex] = this.array[this.length]; //move the last to this spot return item; } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 | # Find the biggest and delete it, Time O(n), Space O(1) def dequeue(self): if (self.length == 0): print("queue is empty") return None maxIndex = 0 for i in range(1, self.length): #search for biggest if (self.array[i] > self.array[maxIndex]): maxIndex = i item = self.array[maxIndex] self.length -= 1 self.array[maxIndex] = self.array[self.length] #move the last to this spot return item |
Peek
Peek is to return the value of the highest priority element. The same as dequeue, we have to find the highest priority element by examining all elements in the array.
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | //Find the biggest and return it, Time O(n), Space O(1) public T peek() { if (length == 0) { System.out.println("The priority queue is empty!"); return null; } int maxIndex = 0; for (int i = 1; i < length; i++) { //search for biggest if (array[i].compareTo (array[maxIndex]) > 0) { maxIndex = i; } } return array[maxIndex]; } |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | //Find the biggest and return it, Time O(n), Space O(1) peek() { if (this.length == 0) { console.log("queue is empty"); return null; } var maxIndex = 0; for (let i = 1; i < this.length; i++) { //search for biggest if (this.array[i] > this.array[maxIndex]) { maxIndex = i; } } return this.array[maxIndex]; } |
Python
1 2 3 4 5 6 7 8 9 10 | #Find the biggest and return it, Time O(n), Space O(1) def peek(self): if (self.length == 0): print("queue is empty") return None maxIndex = 0 for i in range(1, self.length): #search for biggest if (self.array[i] > self.array[maxIndex]): maxIndex = i return self.array[maxIndex] |
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 all, in insert order, Time O(n), Space O(1) public void print() { for (int i = 0; i < length; i++) System.out.print(array[i] + " "); System.out.println(); } |
Javascript
1 2 3 4 5 6 7 | //print all, in insert order, Time O(n), Space O(n) print() { var line = ""; for (let i = 0; i < this.length; i++) line += this.array[i] + " "; console.log(line); } |
Python
1 2 3 4 5 | # print all, in insert order, Time O(n), Space O(1) def print(self): for i in range( 0, self.length, +1): print(self.array[i], end = ' ') print() |
Free download
Download priority queue implementation with array in Java, JavaScript and Python
Data structures introduction PDF
How to implement a priority queue using an array?
There are two ways to implement a priority queue using an array. The first is to implement using an ordered array. All elements are sorted during insertion. The second way is to allow new elements to enter using an unordered array. When dequeue, find the highest priority element by checking all elements.