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.
There are two ways to implement with array. The first is to implement as an ordered array. All element are ordered when insert. To dequeue, remove the last element which has the highest priority. The second way is to allow new element to enter in an arbitrary order. To dequeue, find the highest priority element by checking all elements and remove it. This post is using unordered array.
Part 1 – priority queue implementation with ordered array
Part 2 – priority queue implementation with unordered array
Part 3 – priority queue implementation with heap iterative solution
Part 4 – priority queue implementation with heap recursive solution
Table of Content
Enqueue
To enqueue an element is the same as adding an element in a regular array -add the element at 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 23 |
// Descending priority, the higher the key, the higher the priority @SuppressWarnings({"unchecked"}) public class PriorityQueueArray2<T extends Comparable<T>> { private T[] pqArray; private int length; private int maxSize; public PriorityQueueArray2(int capacity) { maxSize = capacity; pqArray = (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; } pqArray[length] = value; length++; } } |
Javascript
|
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 PriorityQueueArrayUnordered { //Constructor, Time O(1), Space O(1) constructor(capacity) { this.maxSize = capacity; this.pqArray = {}; 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.pqArray[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 key, the higher the priority class PriorityQueueArrayUnordered: # Constructor, Time O(1), Space O(1) def __init__(self, capacity) : self.maxSize = capacity self.pqArray = {} 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.pqArray[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, we have to find the highest priority element first. This requires to exam 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 (pqArray[i].compareTo (pqArray[maxIndex]) > 0) { maxIndex = i; } } T item = pqArray[maxIndex]; System.out.println("dequeue: " + item); length--; pqArray[maxIndex] = pqArray[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.pqArray[i] > this.pqArray[maxIndex]) { maxIndex = i; } } var item = this.pqArray[maxIndex]; this.length--; this.pqArray[maxIndex] = this.pqArray[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.pqArray[i] > self.pqArray[maxIndex]) : maxIndex = i; item = self.pqArray[maxIndex]; self.length -= 1 self.pqArray[maxIndex] = self.pqArray[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 examing 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 (pqArray[i].compareTo (pqArray[maxIndex]) > 0) { maxIndex = i; } } return pqArray[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 (tthis.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.pqArray[i] > this.pqArray[maxIndex]) { maxIndex = i; } } return this.pqArray[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.pqArray[i] > self.pqArray[maxIndex]) : maxIndex = i; return self.pqArray[maxIndex] |
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, in insert order, 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, in insert order, 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, in insert order, 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) |
Download Java, JavaScript and Python code
Priority queue animated visual
Data structures and Java collections