Algorithm
A priority queue is an abstract data type that operates similar to a regular queue or stack but where each element has an associated priority. In a priority queue, elements with higher priorities are served before elements with lower priorities.
Here are the basic operations typically supported by a priority queue:
-
Insertion (Enqueue): Add an element to the priority queue with an associated priority.
-
Deletion (Dequeue): Remove the element with the highest priority from the priority queue.
-
Peek (Front): Retrieve the element with the highest priority without removing it.
Priority queues are often implemented using various data structures such as binary heaps, Fibonacci heaps, or self-balancing binary search trees. The choice of implementation depends on the specific requirements and constraints of the application.
Example:
Let's consider a priority queue of tasks to be executed, where tasks have different priorities. A task with a higher priority should be executed before a task with a lower priority.
plaintext
Priority Queue: 1. Task A (Priority: High) 2. Task B (Priority: Medium) 3. Task C (Priority: Low)
In this example, if we dequeue from the priority queue, we would get Task A first, as it has the highest priority.
Code Examples
#1 Priority Queue Implementations in Python- Using List:
Code -
Python Programming
class PriorityQueueList:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def enqueue(self, item, priority):
entry = (priority, item)
self.items.append(entry)
self.items.sort(reverse=True)
def dequeue(self):
if not self.is_empty():
return self.items.pop()[1]
else:
raise IndexError("Cannot dequeue from an empty priority queue")
# Example usage:
priority_queue = PriorityQueueList()
priority_queue.enqueue("Task 1", 3)
priority_queue.enqueue("Task 2", 1)
priority_queue.enqueue("Task 3", 2)
while not priority_queue.is_empty():
print(priority_queue.dequeue())
#2 Priority Queue Implementations in Python- Using heapq Module:
Code -
Python Programming
import heapq
class PriorityQueueHeapq:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def enqueue(self, item, priority):
entry = (priority, item)
heapq.heappush(self.items, entry)
def dequeue(self):
if not self.is_empty():
return heapq.heappop(self.items)[1]
else:
raise IndexError("Cannot dequeue from an empty priority queue")
# Example usage:
priority_queue = PriorityQueueHeapq()
priority_queue.enqueue("Task 1", 3)
priority_queue.enqueue("Task 2", 1)
priority_queue.enqueue("Task 3", 2)
while not priority_queue.is_empty():
print(priority_queue.dequeue())
#3 Priority Queue Implementations in Java- PriorityQueue without Comparator:
Code -
Java Programming
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
// Creating a PriorityQueue without a Comparator
PriorityQueue < Integer> priorityQueue = new PriorityQueue<>();
// Adding elements to the PriorityQueue
priorityQueue.add(5);
priorityQueue.add(3);
priorityQueue.add(8);
priorityQueue.add(1);
// Removing elements from the PriorityQueue
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
}
}
#4 Priority Queue Implementations in Java- PriorityQueue with Comparator:
Code -
Java Programming
import java.util.PriorityQueue;
import java.util.Comparator;
public class PriorityQueueWithComparator {
public static void main(String[] args) {
// Creating a PriorityQueue with a custom Comparator
PriorityQueue < Integer> priorityQueueWithComparator = new PriorityQueue<>(Comparator.reverseOrder());
// Adding elements to the PriorityQueue
priorityQueueWithComparator.add(5);
priorityQueueWithComparator.add(3);
priorityQueueWithComparator.add(8);
priorityQueueWithComparator.add(1);
// Removing elements from the PriorityQueue
while (!priorityQueueWithComparator.isEmpty()) {
System.out.println(priorityQueueWithComparator.poll());
}
}
}
#5 Priority Queue Implementations in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Structure to represent a priority queue node
typedef struct {
int data;
int priority;
} PriorityQueueNode;
// Structure to represent a priority queue
typedef struct {
PriorityQueueNode *array;
int capacity;
int size;
} PriorityQueue;
// Function to initialize a priority queue
PriorityQueue* createPriorityQueue(int capacity) {
PriorityQueue* queue = (PriorityQueue*)malloc(sizeof(PriorityQueue));
queue->array = (PriorityQueueNode*)malloc(capacity * sizeof(PriorityQueueNode));
queue->capacity = capacity;
queue->size = 0;
return queue;
}
// Function to swap two priority queue nodes
void swap(PriorityQueueNode* a, PriorityQueueNode* b) {
PriorityQueueNode temp = *a;
*a = *b;
*b = temp;
}
// Function to heapify a subtree with the root at the given index
void heapify(PriorityQueue* queue, int index) {
int smallest = index;
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
if (leftChild < queue->size && queue->array[leftChild].priority < queue->ar
#6 Priority Queue Implementations in C++ : Priority Queue using STL
Code -
C++ Programming
#include <iostream>
#include <queue>
int main() {
std::priority_queue < int> maxHeap; // default: max heap
maxHeap.push(30);
maxHeap.push(10);
maxHeap.push(50);
std::cout << "Top element: " << maxHeap.top() << std::endl; // Output: 50
maxHeap.pop();
std::cout << "Top element after pop: " << maxHeap.top() << std::endl; // Output: 30
return 0;
}
#7 Priority Queue Implementations in C++ : Priority Queue using Binary Heap
Code -
C++ Programming
#include <iostream>
#include <vector>
class PriorityQueue {
private:
std::vector<int> heap;
void heapifyUp(int index) {
while (index > 0) {
int parentIndex = (index - 1) / 2;
if (heap[index] > heap[parentIndex]) {
std::swap(heap[index], heap[parentIndex]);
index = parentIndex;
} else {
break;
}
}
}
void heapifyDown(int index) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
int largest = index;
if (leftChild < heap.size() && heap[leftChild] > heap[largest]) {
largest = leftChild;
}
if (rightChild < heap.size() && heap[rightChild] > heap[largest]) {
largest = rightChild;
}
if (largest != index) {
std::swap(heap[index], heap[largest]);
heapifyDown(largest);
}
}
public:
void push(int value) {
heap.push_back(value);
heapifyUp(heap.size() - 1);
}
void pop() {
if (heap.empty()) {
return;
}
std::swap(heap[0], heap[heap.size() - 1]);
heap.pop_back();
heapifyDown(0);
}
int top() const {
if (!heap.empty()) {
return heap[0];
} else {
throw std::out_of_range("Priority queue is empty");
}
}
bool empty() const {
return heap.empty();
}
};
int main() {
PriorityQueue maxHeap;
maxHeap.push(30);
maxHeap.push(10);
maxHeap.push(50);
std::cout << "Top element: " << maxHeap.top() << std::endl; // Output: 50
maxHeap.pop();
std::cout << "Top element after pop: " << maxHeap.top() << std::endl; // Output: 30
return 0;
}
Demonstration
Priority Queue-DevsEnv