C++ Program to Implement a Priority Queue

1. Introduction

A priority queue is a specialized data structure that keeps its elements in sorted order according to their priority. The most crucial element is always at the front, and the least crucial one is at the end. This data structure is particularly useful in algorithms that require repeatedly removing the object with the highest (or lowest) priority. 

In this post, we'll explore how to implement a basic priority queue in C++ using the binary heap data structure.

2. Program Overview

Our priority queue will offer the following functionalities:

1. Inserting an element with a given priority.

2. Extracting the element with the highest priority.

3. Peeking at the element with the highest priority without removing it.

The binary heap will facilitate efficient operations, ensuring that insertion and extraction occur in O(log n) time.

3. Code Program

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

class PriorityQueue {
private:
    vector<int> heap;

    // Function to get the parent index
    int parent(int idx) { return (idx - 1) / 2; }

    // Function to get the left child index
    int leftChild(int idx) { return 2 * idx + 1; }

    // Function to get the right child index
    int rightChild(int idx) { return 2 * idx + 2; }

    // Function to move the element up to maintain heap property
    void siftUp(int idx) {
        while (idx && heap[parent(idx)] < heap[idx]) {
            swap(heap[parent(idx)], heap[idx]);
            idx = parent(idx);
        }
    }

    // Function to move the element down to maintain heap property
    void siftDown(int idx) {
        int left = leftChild(idx);
        int right = rightChild(idx);
        int largest = idx;

        if (left < heap.size() && heap[left] > heap[idx])
            largest = left;
        if (right < heap.size() && heap[right] > heap[largest])
            largest = right;

        if (largest != idx) {
            swap(heap[idx], heap[largest]);
            siftDown(largest);
        }
    }

public:
    // Function to insert an element into the priority queue
    void insert(int val) {
        heap.push_back(val);
        siftUp(heap.size() - 1);
    }

    // Function to extract and return the maximum element from the priority queue
    int extractMax() {
        int maxVal = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        siftDown(0);
        return maxVal;
    }

    // Function to get the maximum element without extracting it
    int getMax() {
        return heap[0];
    }

    // Function to check if the priority queue is empty
    bool isEmpty() {
        return heap.empty();
    }
};

int main() {
    PriorityQueue pq;
    pq.insert(10);
    pq.insert(20);
    pq.insert(5);
    cout << "Max Value: " << pq.extractMax() << endl;  // Outputs: 20
    cout << "Max Value: " << pq.getMax() << endl;      // Outputs: 10
    return 0;
}

Output:

Max Value: 20
Max Value: 10

4. Step By Step Explanation

1. Our PriorityQueue class maintains an internal vector, heap, which stores the elements in a way that represents a binary heap.

2. For any given index, its parent, left child, and right child are computed using helper methods.

3. siftUp ensures that a newly inserted element finds its correct position in the heap.

4. siftDown ensures that after the maximum element is removed, the heap property is restored by pushing the root element to its correct position.