Priority queue implementation using queues in C++

10 Oct 2023

tech

A priority queue is a data structure where each element has a priority assigned to it. The elements in the queue are always ordered according to their priority, and the element with the highest priority is dequeued first. Priority queues are commonly used in algorithms such as Dijkstra’s algorithm and Huffman coding.

In this article, we will implement a priority queue using queues in C++. We will use two queues to implement the priority queue: one queue to store the elements and another queue to store the priorities for each element.

Implementation Steps

Include the necessary header files:

#include <iostream>
#include <queue>
using namespace std;

Define a struct to hold elements and priorities together:

struct Element {
  int value;
  int priority;
};

Create a comparison function to compare the priorities of two elements:

struct Compare {
  bool operator()(const Element& a, const Element& b) {
 return a.priority < b.priority;
  }
};

Create a priority queue using the priority_queue template class and the comparison function:
```
priority_queue<Element, vector<Element>, Compare> pq;
```
Enqueue an element with its priority:
```
Element e1 = {5, 2};
pq.push(e1);
```

Dequeue the element with the highest priority:

Element highestPriorityElement = pq.top();
pq.pop();

Print the value and priority of the dequeued element:

cout << "Value: " << highestPriorityElement.value << endl;
cout << "Priority: " << highestPriorityElement.priority << endl;

Example Usage

int main() {
  priority_queue<Element, vector<Element>, Compare> pq;

  Element e1 = {5, 2};
  Element e2 = {10, 1};
  Element e3 = {3, 3};
  
  pq.push(e1);
  pq.push(e2);
  pq.push(e3);

  Element highestPriorityElement = pq.top();
  pq.pop();
  
  cout << "Value: " << highestPriorityElement.value << endl;
  cout << "Priority: " << highestPriorityElement.priority << endl;
  
  return 0;
}

Conclusion

In this article, we implemented a priority queue using queues in C++. By using two queues and a comparison function, we were able to maintain the order of elements based on their priorities. Priority queues are a powerful data structure for dealing with elements that have different priorities, and they find various applications in computer science and algorithms.

#tech #C++