Max Heap By Priority Queue

#include <bits/stdc++.h> // Includes common standard libraries, including <queue> for priority_queue
using namespace std;     // Use the standard namespace

int main() {
    // Declares a priority_queue of integers.
    // By default, std::priority_queue<int> acts as a MAX HEAP.
    // This means the largest element will always be at the top.
    priority_queue<int> maxHeap;

    // --- Insertion Operations ---
    // push() adds an element to the heap while maintaining the heap property.
    // Time complexity for push: O(log N)
    maxHeap.push(52);
    maxHeap.push(50);
    maxHeap.push(54);
    maxHeap.push(40);
    maxHeap.push(35);
    maxHeap.push(65); // After this, 65 is the largest, so it should be at the top.

    // --- Accessing Top Element ---
    // top() returns a reference to the element at the top (highest priority).
    // It does NOT remove the element.
    // Time complexity for top: O(1)
    cout << "Top element : " << maxHeap.top() << endl; // Expected: 65

    // --- Deletion Operation ---
    // pop() removes the element at the top (highest priority).
    // It does NOT return the element. You must call top() first if you need its value.
    // Time complexity for pop: O(log N)
    maxHeap.pop(); // Removes 65. The next largest (54) will become the new top.
    cout << "Top element : " << maxHeap.top() << endl; // Expected: 54

    maxHeap.pop(); // Removes 54.
    maxHeap.pop(); // Removes 52. The next largest (50) will become the new top.
    cout << "Top element : " << maxHeap.top() << endl; // Expected: 50

    // --- Checking if empty ---
    // empty() returns true if the priority queue contains no elements, false otherwise.
    // Time complexity for empty: O(1)
    if(maxHeap.empty()) {
        cout << "Max Heap is empty!" << endl;
    } else {
        cout << "Max Heap is NOT empty! Current size: " << maxHeap.size() << endl; // Expected: 3 elements remaining (50, 40, 35)
    }

    // --- Demonstrate emptying and checking again ---
    maxHeap.pop(); // Removes 50
    maxHeap.pop(); // Removes 40
    maxHeap.pop(); // Removes 35
    if(maxHeap.empty()) {
        cout << "Max Heap is now empty after popping all elements!" << endl; // Expected: Max Heap is now empty!
    }

    return 0;
}

/*
Sample Output:

Top element : 65
Top element : 54
Top element : 50
Max Heap is NOT empty! Current size: 3
Max Heap is now empty after popping all elements!
*/

1. What is std::priority_queue?

• std::priority_queue is a container adapter in C++‘s Standard Template Library (STL).
• It provides a data structure that always keeps its elements sorted based on some priority.
• By default, it implements a Max Heap, meaning the element with the highest value (priority) is always at the top.
• It is typically implemented using a std::vector as its underlying container and std::make_heap / std::push_heap / std::pop_heap algorithms internally to maintain the heap property.

2. Key Operations & Usage

• Header: Include <queue> (though <bits/stdc++.h> covers it).
• Default Behavior: priority_queue<Type> creates a Max Heap.
  • Type: Data type of elements (e.g., int, string, custom objects).
  • std::vector<Type> (default underlying container): The container used to store elements.
  • std::less<Type> (default comparator): Defines the “less than” relationship, ensuring the largest element is at the top.

Common Member Functions:

• push(const T& value):
  • Inserts value into the priority queue.
  • Maintains the heap property.
  • Time Complexity: O(log N) (N is number of elements).
• top():
  • Returns a const reference to the element with the highest priority (the maximum element in a Max Heap).
  • Does not remove the element.
  • Time Complexity: O(1).
  • Caution: Calling top() on an empty priority queue results in undefined behavior.
• pop():
  • Removes the element with the highest priority (the maximum element).
  • Maintains the heap property.
  • Time Complexity: O(log N).
  • Caution: Calling pop() on an empty priority queue results in undefined behavior.
• empty():
  • Returns true if the priority queue is empty, false otherwise.
  • Time Complexity: O(1).
• size():
  • Returns the number of elements in the priority queue.
  • Time Complexity: O(1).

3. Creating a Min Heap with std::priority_queue

• To create a Min Heap (where the smallest element is at the top), you need to specify a custom comparator:

  priority_queue<int, vector<int>, greater<int>> minHeap;

  • greater<int> is a function object that defines “greater than”, causing the smallest element to have the highest “priority” (i.e., come to the top).

---