Priority Queue Implementation in CPP

1. Introduction

A Priority Queue is an advanced data structure that serves elements based on their priorities. Instead of serving elements on a first-come, first-serve basis like the regular queue, a priority queue serves elements based on their priority. If elements with the same priority occur, they are served according to their order in the queue.

2. Implementation Steps

1. Decide on the strategy for priority (e.g., a higher number means a higher priority).

2. Initialize the priority queue. You can use a list, heap, or other data structures for this.

3. Implement the insert operation to add an element with a given priority to the priority queue.

4. Implement the deleteHighestPriority operation to remove and return the element with the highest priority.

5. Implement a method to peek the highest priority element without removing it.

6. Ensure that if two elements have the same priority, they are served based on their order of insertion.

3. Implementation in C++ Programming

#include <iostream>
#include <queue>
using namespace std;
class PriorityQueue {
private:
    // Using STL's priority_queue
    priority_queue<int> pq;
    
public:
    void insert(int x) {
        pq.push(x);  // Simply insert an element
    }
    
    int deleteHighestPriority() {
        if (pq.empty()) {
            cout << "Priority Queue is empty";
            return -1;
        } else {
            int top = pq.top();  // Get the top element
            pq.pop();  // Remove the top element
            return top;
        }
    }
    
    int peek() {
        if (pq.empty()) {
            cout << "Priority Queue is empty";
            return -1;
        } else {
            return pq.top();  // Return the top element without removal
        }
    }
    
    bool isEmpty() {
        return pq.empty();
    }
};

// Client code to test the priority queue implementation
int main() {
    PriorityQueue pq;
    pq.insert(10);
    pq.insert(20);
    pq.insert(15);
    cout << pq.deleteHighestPriority() << " Deleted from priority queue\n";
    cout << "Highest priority element is " << pq.peek() << endl;
    return 0;
}

Output:

20 Deleted from priority queue
Highest priority element is 15

Explanation:

1. The PriorityQueue class uses the Standard Template Library's (STL) priority_queue for the implementation. This structure internally uses a max-heap to ensure the highest priority element is always on the top.

2. The insert function directly pushes the element onto the priority_queue.

3. The deleteHighestPriority function checks if the priority queue is empty. If not, it returns and removes the topmost element (highest priority). Otherwise, it indicates that the "Priority Queue is empty".

4. The peek function returns the topmost element without removing it.

5. The isEmpty function checks if the priority queue is empty by calling the empty method of priority_queue.

6. In the client code, elements are added to the priority queue, and then the highest priority element is deleted. The program also demonstrates checking the highest priority element using the peek function.