Are you familiar with containers like a heap?

Yes, I am familiar. A heap is a specialized tree that satisfies the heap property: for any node, its value must be greater than or equal to (or less than or equal to) the values of its children.

There are:

• Max-heap: The value of the parent node is always greater than or equal to the values of its children. The maximum element is at the root.
• Min-heap: The value of the parent node is always less than or equal to the values of its children. The minimum element is at the root.

A common implementation of a heap is a binary heap, which is usually represented as an array. The parent-child relationship is determined by array indices:

• The left child of the element at index i is at index 2*i + 1.
• The right child of the element at index i is at index 2*i + 2.
• The parent of the element at index i is at index (i - 1) / 2.

Main operations and their time complexities (for binary heaps):

Operation	Time Complexity
Creating a heap	O(n)
Inserting an element	O(log n)
Removing max/min	O(log n)
Extracting max/min	O(log n)
Peek at the top	O(1)

Applications of heaps:

• Implementation of priority queues.
• Heap sort algorithm.
• Graph algorithms (e.g., Dijkstra's algorithm, Prim's algorithm).

In C++, the standard library provides std::priority_queue, which is a container adapter that by default uses std::vector as the underlying container and implements a max-heap.

#include <queue>
#include <vector>
#include <iostream>

int main() {
    // Creating a priority queue (max-heap by default)
    std::priority_queue<int> max_heap;

    // Adding elements
    max_heap.push(10);
    max_heap.push(30);
    max_heap.push(20);
    max_heap.push(5);

    // Extracting elements (in descending order)
    while (!max_heap.empty()) {
        std::cout << max_heap.top() << " "; // Peek at the top
        max_heap.pop(); // Remove the top
    }
    std::cout << std::endl;

    // Creating a min-heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

    min_heap.push(10);
    min_heap.push(30);
    min_heap.push(20);
    min_heap.push(5);

    // Extracting elements (in ascending order)
    while (!min_heap.empty()) {
        std::cout << min_heap.top() << " ";
        min_heap.pop();
    }
    std::cout << std::endl;

    return 0;
}