Priority Queue

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

int main() {
    // Max heap (default - largest element at top)
    priority_queue<int> pq;
    
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);
    pq.push(40);
    
    cout << "Priority Queue (Max Heap):" << endl;
    cout << "Top element (maximum): " << pq.top() << endl;
    
    cout << "\nElements in descending order:" << endl;
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    
    // Min heap
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    minHeap.push(30);
    minHeap.push(10);
    minHeap.push(50);
    minHeap.push(20);
    minHeap.push(40);
    
    cout << "\nPriority Queue (Min Heap):" << endl;
    cout << "Top element (minimum): " << minHeap.top() << endl;
    
    cout << "\nElements in ascending order:" << endl;
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;
    
    // Custom comparator
    auto cmp = [](int a, int b) { return a > b; };
    priority_queue<int, vector<int>, decltype(cmp)> customPQ(cmp);
    
    customPQ.push(5);
    customPQ.push(2);
    customPQ.push(8);
    
    cout << "\nCustom Priority Queue:" << endl;
    while (!customPQ.empty()) {
        cout << customPQ.top() << " ";
        customPQ.pop();
    }
    cout << endl;
    
    return 0;
}

Priority Queue (Max Heap):
Top element (maximum): 50

Elements in descending order:
50 40 30 20 10

Priority Queue (Min Heap):
Top element (minimum): 10

Elements in ascending order:
10 20 30 40 50

Custom Priority Queue:
2 5 8

This program teaches you how to use Priority Queue in C++. Priority queue is a container that provides constant-time access to the largest (or smallest) element. By default, it's a max heap, but can be configured as a min heap. It's essential for algorithms requiring priority-based processing.

---

1. What This Program Does

The program demonstrates priority queue operations:

• Max heap (default - largest at top)
• Min heap (smallest at top)
• Custom comparators
• Priority-based element access

Priority queues provide efficient access to highest/lowest priority elements.

---

2. Header Files Used

1. #include <iostream>

   • Provides cout and cin for input/output operations.

2. #include <queue>

   • Provides priority_queue container class.

3. #include <vector>

   • Provides vector for priority_queue implementation.

---

3. Understanding Priority Queue

Heap Concept:

• Binary heap data structure
• Root contains max (or min) element
• Maintains heap property
• Efficient priority access

Key Features:

• O(1) access to top element
• O(log n) insert/delete
• Max heap (default) or min heap
• Priority-based ordering

---

4. Max Heap (Default)

Declaration:

priority_queue<int> pq;

Operations:

pq.push(30); // Insert pq.top(); // Access maximum pq.pop(); // Remove maximum

How it works:

• Largest element always at top
• Maintains max heap property
• O(log n) insert/delete
• O(1) top access

---

5. Min Heap

Declaration:

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

How it works:

• Template: priority_queue<Type, Container, Comparator>
• greater<int>: makes it min heap
• Smallest element at top
• Useful for finding minimum

---

6. Custom Comparator

Lambda Comparator:

auto cmp = [](int a, int b) { return a > b; }; priority_queue<int, vector<int>, decltype(cmp)> customPQ(cmp);

How it works:

• Custom comparison function
• Defines priority order
• Flexible ordering
• Can use any comparison logic

---

7. When to Use Priority Queue

Best For:

• Dijkstra's algorithm
• Heap sort
• Task scheduling by priority
• Finding k largest/smallest
• Event simulation
• Merge k sorted lists

Example Scenarios:

• Shortest path algorithms
• Top K elements
• Priority-based scheduling
• Median finding
• Huffman coding

---

8. Important Considerations

Heap Property:

• Max heap: parent >= children
• Min heap: parent <= children
• Maintained automatically
• Top element always max/min

Performance:

• Top access: O(1)
• Insert: O(log n)
• Delete: O(log n)
• Efficient for priority operations

No Random Access:

• Only top element accessible
• Must pop to access other elements
• Use other containers if random access needed

---

9. return 0;

This ends the program successfully.

---

Summary

• Priority queue: provides O(1) access to largest (max heap) or smallest (min heap) element.
• Default: max heap (largest at top).
• Min heap: use greater<int> comparator.
• Operations: push(), pop(), top(), empty(), size().
• Implemented as binary heap, O(log n) insert/delete.
• Understanding priority queues enables efficient priority-based processing.
• Essential for algorithms requiring priority access like Dijkstra's and scheduling.

This program is fundamental for learning heap data structures, understanding priority-based algorithms, and preparing for advanced graph algorithms and scheduling problems in C++ programs.