Priority Queue
Overview
A priority queue is... (you've guessed it) - a queue with priorities. It allows you to store elements in a way that the highest (or lowest) priority item can be efficiently accessed and removed.
Imagine a queue like a line of people waiting to enter an event. In a regular queue, the first person who arrived would be the first to enter. However, in a priority queue, each person has a ticket with a priority number, and the person with the highest (or lowest) number gets to enter ahead of others. Or even more extreme scenario - a famous movie star with highest priority comes in and bypasses everyone in the queue and enters first.
The essential operations of a priority queue are:
Insertion: Simply adding an element with a specific priority in the queue.
Extraction: You can remove and retrieve the element with the highest (or lowest) priority from the queue.
The beauty of a priority queue lies in its ability to provide quick access to the element with the highest (or lowest) priority, which makes it perfect for scenarios where tasks must be handled based on their urgency or importance. Tasks with higher priorities are addressed before those with lower priorities. This is incredibly useful in various applications, such as task scheduling, network routing, and simulation systems.
It's important to know that priority queue is usually based on heap data structure (See Trees -> Heap). In the Python example below, we have used e premade heap (import heapq) while, for instance, in the JavaScript example, we have a custom min-heap based priority queue implementation. It's important to be aware of both examples - using ready language constructs or implementing everything from scratch yourself.
If you have any doubts on the 'heap' concepts, leave these examples aside and, again, wait to learn Heaps in the Trees section and then get back here.
import heapq
# Step 1: Create the initial priority queue with elements 4, 1, 3, 5, 7, 9
priority_queue = [4, 1, 3, 5, 7, 9]
# Step 2: Move 4 to its correct position by its priority (heapify again)
heapq.heapify(priority_queue)
# Step 3: Dequeue 9
dequeued_element1 = heapq.heappop(priority_queue)
# Step 4: Dequeue 7
dequeued_element2 = heapq.heappop(priority_queue)
# Step 5: Dequeue 5
dequeued_element3 = heapq.heappop(priority_queue)
# Step 6: Enqueue new element 10 and move it to its correct position
heapq.heappush(priority_queue, 10)
heapq.heapify(priority_queue)
# Step 7: Dequeue all remaining elements
while priority_queue:
dequeued_element = heapq.heappop(priority_queue)
print("Dequeued:", dequeued_element)
print("Priority Queue is now empty.")
class PriorityQueue {
constructor() {
this.data = [];
}
enqueue(element) {
this.data.push(element);
this.bubbleUp(this.data.length - 1);
}
bubbleUp(index) {
const element = this.data[index];
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
const parent = this.data[parentIndex];
if (element >= parent) break;
this.data[parentIndex] = element;
this.data[index] = parent;
index = parentIndex;
}
}
dequeue() {
if (this.data.length === 0) return null;
if (this.data.length === 1) return this.data.pop();
const min = this.data[0];
this.data[0] = this.data.pop();
this.bubbleDown(0);
return min;
}
bubbleDown(index) {
const length = this.data.length;
const element = this.data[index];
while (true) {
const leftChildIndex = 2 * index + 1;
const rightChildIndex = 2 * index + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.data[leftChildIndex];
if (leftChild < element) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.data[rightChildIndex];
if (
(swap === null && rightChild < element) ||
(swap !== null && rightChild < leftChild)
) {
swap = rightChildIndex;
}
}
if (swap === null) break;
this.data[index] = this.data[swap];
this.data[swap] = element;
index = swap;
}
}
isEmpty() {
return this.data.length === 0;
}
}
// Initial priority queue with elements 4, 1, 3, 5, 7, 9
const priorityQueue = new PriorityQueue();
priorityQueue.enqueue(4);
priorityQueue.enqueue(1);
priorityQueue.enqueue(3);
priorityQueue.enqueue(5);
priorityQueue.enqueue(7);
priorityQueue.enqueue(9);
console.log("Initial Priority Queue:", priorityQueue.data);
// Move 4 to its correct position by re-enqueueing it
priorityQueue.enqueue(priorityQueue.dequeue());
console.log("Priority Queue with 4 moved to its correct position:", priorityQueue.data);
// Dequeue 9
const dequeuedElement1 = priorityQueue.dequeue();
console.log("Dequeued:", dequeuedElement1);
console.log("Priority Queue after dequeuing 9:", priorityQueue.data);
// Dequeue 7
const dequeuedElement2 = priorityQueue.dequeue();
console.log("Dequeued:", dequeuedElement2);
console.log("Priority Queue after dequeuing 7:", priorityQueue.data);
// Dequeue 5
const dequeuedElement3 = priorityQueue.dequeue();
console.log("Dequeued:", dequeuedElement3);
console.log("Priority Queue after dequeuing 5:", priorityQueue.data);
// Enqueue 10 and move it to its correct position
priorityQueue.enqueue(10);
console.log("Priority Queue after enqueueing 10:", priorityQueue.data);
// Dequeue all remaining elements
while (!priorityQueue.isEmpty()) {
const dequeuedElement = priorityQueue.dequeue();
console.log("Dequeued:", dequeuedElement);
}
console.log("Priority Queue is now empty.");
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
// Initial priority queue with elements 4, 1, 3, 5, 7, 9
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(4);
priorityQueue.add(1);
priorityQueue.add(3);
priorityQueue.add(5);
priorityQueue.add(7);
priorityQueue.add(9);
System.out.println("Initial Priority Queue: " + priorityQueue);
// Move 4 to its correct position by removing and adding it back
priorityQueue.remove(4);
priorityQueue.add(4);
System.out.println("Priority Queue with 4 moved to its correct position: " + priorityQueue);
// Dequeue 9
int dequeuedElement1 = priorityQueue.poll();
System.out.println("Dequeued: " + dequeuedElement1);
System.out.println("Priority Queue after dequeuing 9: " + priorityQueue);
// Dequeue 7
int dequeuedElement2 = priorityQueue.poll();
System.out.println("Dequeued: " + dequeuedElement2);
System.out.println("Priority Queue after dequeuing 7: " + priorityQueue);
// Dequeue 5
int dequeuedElement3 = priorityQueue.poll();
System.out.println("Dequeued: " + dequeuedElement3);
System.out.println("Priority Queue after dequeuing 5: " + priorityQueue);
// Enqueue 10 and move it to its correct position
priorityQueue.add(10);
System.out.println("Priority Queue after enqueueing 10: " + priorityQueue);
// Dequeue all remaining elements
while (!priorityQueue.isEmpty()) {
int dequeuedElement = priorityQueue.poll();
System.out.println("Dequeued: " + dequeuedElement);
}
System.out.println("Priority Queue is now empty.");
}
}
#include <stdio.h>
#include <stdlib.h>
// Function to swap two integers
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to heapify the array (min-heap)
void heapify(int arr[], int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest]) {
smallest = left;
}
if (right < n && arr[right] < arr[smallest]) {
smallest = right;
}
if (smallest != i) {
swap(&arr[i], &arr[smallest]);
heapify(arr, n, smallest);
}
}
// Function to build the min-heap
void buildHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
}
// Function to extract the minimum element from the heap
int extractMin(int arr[], int* n) {
if (*n == 0) {
return -1; // Empty heap
}
int min = arr[0];
arr[0] = arr[*n - 1];
(*n)--;
heapify(arr, *n, 0);
return min;
}
int main() {
int n = 6;
int priority_queue[] = {4, 1, 3, 5, 7, 9};
// Step 2: Move 4 to its correct position by rebuilding the heap
buildHeap(priority_queue, n);
// Step 3: Dequeue 9
int dequeued_element1 = extractMin(priority_queue, &n);
// Step 4: Dequeue 7
int dequeued_element2 = extractMin(priority_queue, &n);
// Step 5: Dequeue 5
int dequeued_element3 = extractMin(priority_queue, &n);
// Step 6: Enqueue new element 10 and move it to its correct position
priority_queue[n++] = 10;
buildHeap(priority_queue, n);
// Step 7: Dequeue all remaining elements
for (int i = 0; i < n; i++) {
int dequeued_element = extractMin(priority_queue, &n);
printf("Dequeued: %d\n", dequeued_element);
}
printf("Priority Queue is now empty.\n");
return 0;
}
class PriorityQueue {
private $queue = [];
public function enqueue($item, $priority) {
$this->queue[] = ['item' => $item, 'priority' => $priority];
usort($this->queue, function ($a, $b) {
return $a['priority'] - $b['priority'];
});
}
public function dequeue() {
if (!$this->isEmpty()) {
return array_shift($this->queue)['item'];
}
return null;
}
public function isEmpty() {
return empty($this->queue);
}
}
$initialInput = [4, 1, 3, 5, 7, 9];
$priorityQueue = new PriorityQueue();
// Enqueue elements
foreach ($initialInput as $element) {
$priorityQueue->enqueue($element, $element);
}
// Move 4 to its correct position
$priorityQueue->enqueue(4, 4);
// Dequeue elements 9, 7, and 5
$dequeuedItems = [];
$dequeuedItems[] = $priorityQueue->dequeue();
$dequeuedItems[] = $priorityQueue->dequeue();
$dequeuedItems[] = $priorityQueue->dequeue();
// Enqueue a new element 10
$priorityQueue->enqueue(10, 10);
// Dequeue 10 and all remaining elements
$remainingItems = [];
while (!$priorityQueue->isEmpty()) {
$remainingItems[] = $priorityQueue->dequeue();
}
// Output the results
echo "Dequeued items: " . implode(', ', $dequeuedItems) . "\n";
echo "Remaining items: " . implode(', ', $remainingItems) . "\n";