A priority queue is a special type of queue in which each element is associated with a priority and the element with the highest priority is served before the others. Priority queues are widely used in scenarios such as CPU scheduling, bandwidth management in network routers, and many more. This article will guide you through different C++ Program to Implement a Priority Queue, providing multiple solutions and example outputs for each approach.
Prerequisites
To effectively follow along with this article, you should have:
- Basic understanding of the C++ programming language.
- Familiarity with standard libraries in C++.
- Understanding of data structures, especially queues and heaps.
Introduction
In this article, we will discuss how to implement a priority queue in C++. We will cover three different methods: using the STL priority queue, implementing a priority queue using a heap, and creating a priority queue with a linked list. Each method will be explained with a code example and output to illustrate the concept.
1. Method 1: Using STL Priority Queue
1.1 Explanation
The Standard Template Library (STL) in C++ provides a ready-made priority queue class. The std::priority_queue is implemented using a max-heap by default, where the largest element has the highest priority.
1.2 Code Implementation
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
pq.push(5);
pq.push(1);
cout << "Priority Queue (using STL): ";
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}
1.3 Output
Priority Queue (using STL): 30 20 10 5 1
2. Method 2: Implementing Priority Queue Using a Heap
2.1 Explanation
A heap is a binary tree-based data structure that satisfies the heap property. The heap property states that the key at the root must be the largest (max-heap) or smallest (min-heap) among all keys present in the binary heap. This property makes heaps suitable for implementing priority queues.
2.2 Code Implementation
#include <iostream>
#include <vector>
using namespace std;
class PriorityQueue {
vector<int> heap;
void heapify_up(int index) {
if (index && heap[parent(index)] < heap[index]) {
swap(heap[index], heap[parent(index)]);
heapify_up(parent(index));
}
}
void heapify_down(int index) {
int left = leftChild(index);
int right = rightChild(index);
int largest = index;
if (left < size() && heap[left] > heap[largest])
largest = left;
if (right < size() && heap[right] > heap[largest])
largest = right;
if (largest != index) {
swap(heap[index], heap[largest]);
heapify_down(largest);
}
}
public:
unsigned int size() {
return heap.size();
}
bool empty() {
return size() == 0;
}
void push(int element) {
heap.push_back(element);
heapify_up(size() - 1);
}
void pop() {
try {
if (size() == 0)
throw out_of_range("Heap underflow");
heap[0] = heap.back();
heap.pop_back();
heapify_down(0);
} catch (const out_of_range& e) {
cout << e.what() << endl;
}
}
int top() {
try {
if (size() == 0)
throw out_of_range("Heap underflow");
return heap.front();
} catch (const out_of_range& e) {
cout << e.what() << endl;
}
return -1;
}
private:
int parent(int index) {
return (index - 1) / 2;
}
int leftChild(int index) {
return (2 * index + 1);
}
int rightChild(int index) {
return (2 * index + 2);
}
};
int main() {
PriorityQueue pq;
pq.push(10);
pq.push(30);
pq.push(20);
pq.push(5);
pq.push(1);
cout << "Priority Queue (using Heap): ";
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}
2.3 Output
Priority Queue (using Heap): 30 20 10 5 1
3. Method 3: Priority Queue Using Linked List
3.1 Explanation
A linked list can also be used to implement a priority queue. In this method, we maintain a sorted linked list where the highest priority element is always at the head of the list.
3.2 Code Implementation
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class PriorityQueue {
Node* front;
public:
PriorityQueue() {
front = nullptr;
}
void push(int element) {
Node* temp = new Node();
temp->data = element;
if (front == nullptr || front->data <= element) {
temp->next = front;
front = temp;
} else {
Node* current = front;
while (current->next != nullptr && current->next->data > element) {
current = current->next;
}
temp->next = current->next;
current->next = temp;
}
}
void pop() {
if (front == nullptr) {
cout << "Priority Queue is empty" << endl;
return;
}
Node* temp = front;
front = front->next;
delete temp;
}
int top() {
if (front == nullptr) {
cout << "Priority Queue is empty" << endl;
return -1;
}
return front->data;
}
bool empty() {
return front == nullptr;
}
};
int main() {
PriorityQueue pq;
pq.push(10);
pq.push(30);
pq.push(20);
pq.push(5);
pq.push(1);
cout << "Priority Queue (using Linked List): ";
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}
3.3 Output
Priority Queue (using Linked List): 30 20 10 5 1
Conclusion
In this article, we explored different methods to implement a priority queue in C++. We started with the simplest approach using the STL priority queue, which is efficient and easy to use. Next, we implemented a priority queue using a heap, providing more control over the internal workings. Finally, we demonstrated how to implement a priority queue using a linked list, showcasing an alternative approach that maintains a sorted order of elements. Understanding these techniques will enhance your ability to handle priority-based operations in various applications, ensuring that you can choose the best method for your specific needs. Priority queues are essential in many algorithms and applications, and mastering their implementation is crucial for any programmer.