Lecture 330:- Heap as Priority Queue

A Heap data structure can be used as the underlying implementation for a Priority Queue. A Priority Queue is an abstract data type that allows elements to be inserted with an associated priority, and it allows retrieval of the element with the highest (in a max-priority queue) or lowest (in a min-priority queue) priority efficiently.

Using a Heap to implement a Priority Queue has the advantage of providing efficient operations for both insertion and extraction of the highest (or lowest) priority element. The complexity of these operations in a Heap-based Priority Queue is as follows:

1. Insertion: O(log n)
   • Inserting an element into the Heap takes logarithmic time as it involves performing a "bubble-up" operation to maintain the heap property.
2. Extraction of the highest (max-priority queue) or lowest (min-priority queue) priority element: O(log n)
   • Extracting the highest or lowest priority element from the Heap also takes logarithmic time as it involves performing a "bubble-down" operation after removing the root element.

Here's a C++ implementation of a Max-Priority Queue using a Heap:

cppCopy code

#include <iostream> #include <vector> using namespace std; class MaxPriorityQueue { private:    vector<int> heap;    void maxHeapify(int index) {        int largest = index;        int leftChild = 2 * index + 1;        int rightChild = 2 * index + 2;        if (leftChild < heap.size() && heap[leftChild] > heap[largest])            largest = leftChild;        if (rightChild < heap.size() && heap[rightChild] > heap[largest])            largest = rightChild;        if (largest != index) {            swap(heap[index], heap[largest]);            maxHeapify(largest);        }    } public:    void insert(int element) {        heap.push_back(element);        int index = heap.size() - 1;        while (index > 0 && heap[index] > heap[(index - 1) / 2]) {            swap(heap[index], heap[(index - 1) / 2]);            index = (index - 1) / 2;        }    }    int extractMax() {        if (heap.empty()) {            cerr << "Priority Queue is empty." << endl;            return -1;        }        int maxElement = heap[0];        heap[0] = heap.back();        heap.pop_back();        maxHeapify(0);        return maxElement;    }    bool isEmpty() const {        return heap.empty();    } }; int main() {    MaxPriorityQueue pq;    pq.insert(20);    pq.insert(10);    pq.insert(30);    pq.insert(5);    while (!pq.isEmpty()) {        cout << "Extracted Max: " << pq.extractMax() << endl;    }    return 0; }

In this implementation, the MaxPriorityQueue class uses a max heap to implement the Priority Queue. The insert function inserts an element into the heap with appropriate "bubble-up" operations. The extractMax function removes the maximum element from the heap (root of the max heap) and performs "bubble-down" operations to maintain the heap property. The isEmpty function checks if the Priority Queue is empty.

Note that you can use a similar approach to create a Min-Priority Queue using a min heap by changing the comparison conditions accordingly.