A priority queue is a queue in which you 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. This priority queue implementation provides code to implement a priority queue using an ordered array. The time complexity of enqueue is O(n), and that of dequeue is O(1).
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
To enqueue an element in a priority queue is the same as adding an element in a sorted array. You can put the highest key 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 24 25 26 27 28 |
// Descending priority, the higher the value, the higher the priority @SuppressWarnings({"unchecked"}) public class PriorityQueueOrderedArray<T extends Comparable<T>> { private int maxSize; private T[] array; //use array to implement private int length = 0; //Constructor, Time O(1), Space O(1) public PriorityQueueOrderedArray(int capacity) { this.maxSize = capacity; this.array = (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(array[i]) < 0) { //biggest put at the end array[i+1] = array[i]; i--; } array[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 PriorityQueueOrderedArray { //Constructor, Time O(1), Space O(1) constructor(capacity) { this.maxSize = capacity; this.array = []; 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.array[i]) { // biggest put at the end this.array[i+1] = this.array[i]; i--; } this.array[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 value, the higher the priority class PriorityQueueOrderedArray: # Constructor, Time O(1), Space O(1) def __init__(self, capacity): self.maxSize = capacity self.array = [None]*capacity 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.array[i]): # biggest put at the end self.array[i+1] = self.array[i] i -= 1 self.array[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, you can just remove the last element.
Java
|
1 2 3 4 5 6 7 8 9 10 |
//Remove from the end, Time O(1), Space O(1) public T dequeue() { if (length == 0) { System.out.println("queue is empty"); return null; } T item = array[length - 1]; length--; return item; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 |
//Remove from the end, Time O(1), Space O(1) dequeue() { if (this.length == 0) { console.log("queue is empty"); return null; } var item = this.array[this.length-1]; this.length--; return item; } |
Python
|
1 2 3 4 5 6 7 8 |
# Remove from the end, Time O(1), Space O(1) def dequeue(self): if (self.length == 0): print("queue is empty") return None item = self.array[self.length-1] self.length -= 1 return item |
Peek
Peek is to return the value of the highest priority element. You simply return the value of the element at the 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 (length == 0) { System.out.println("queue is empty"); return null; } return array[length-1]; } |
Javascript
|
1 2 3 4 5 6 7 8 |
//Return the end value, Time O(1), Space O(1) peek() { if (this.length == 0) { console.log("queue is empty"); return null; } return this.array[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.length == 0): print("queue is empty") return None return self.array[self.length-1] |
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, they are sorted, 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 sorted, 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, they are sorted, 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 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. A 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.