Implement a priority queue using a heap

A priority queue is a data structure that maintains a set of elements, each associated with a priority. The basic operations on a priority queue typically include insertion (enqueue) and extraction of the highest-priority element (dequeue).

Table of Contents

Priority Queue using Binary Heap:

A priority queue implemented using a binary heap is a common and efficient data structure. A binary heap is a complete binary tree where the value of each node is less than or equal to the values of its children. For a max heap, the root has the maximum value, and for a min heap, the root has the minimum value.

Insertion (Enqueue):
- Add the new element to the bottom level of the heap.
- Then, “heapify up” by swapping the new element with its parent until the heap order property is restored.
Extraction (Dequeue):
- The highest-priority element is at the root of the heap.
- Replace the root with the last element in the heap.
- “Heapify down” by swapping the new root with its larger (for max heap) or smaller (for min heap) child until the heap order property is restored.

Time Complexity:

Insertion:
- O(log n), where n is the number of elements in the heap.
- Due to the height of the binary heap.
Extraction:
- O(log n), where n is the number of elements in the heap.
- Due to the height of the binary heap.

Priority queue using heap in C++

#include <iostream>
#include <vector>

class MaxHeap {
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()) {
            std::swap(heap[0], heap.back());
            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();
    }

    size_t size() const {
        return heap.size();
    }
};

int main() {
    MaxHeap maxHeap;

    maxHeap.push(5);
    maxHeap.push(2);
    maxHeap.push(8);
    maxHeap.push(1);

    std::cout << "Current max heap size: " << maxHeap.size() << std::endl;
    std::cout << "Top element: " << maxHeap.top() << std::endl;

    maxHeap.pop();
    std::cout << "After popping, new top element: " << maxHeap.top() << std::endl;

    return 0;
}

Output:

Current max heap size: 4
Top element: 8
After popping, new top element: 5