C++ Heap or Priority Queues

A heap is a specialized binary tree-based data structure. It is a complete binary tree (all levels are completely filled except possibly the last one, which is filled from left to right) where each node satisfies the heap property. The heap property states that the value of each node is either greater than or equal to (max heap) or less than or equal to (min heap) the values of its children.

Heaps are mainly used to efficiently maintain the largest (max heap) or smallest (min heap) elements in constant time (top of the heap). This makes heaps valuable for priority queues and sorting algorithms like Heap Sort.

Types of Heap

There are two main types of heaps: min-heap and max-heap.

Min-Heap

In a min-heap, the value of each node is smaller than or equal to the values of its children. Therefore, the root node contains the minimum value in the heap.

Max-Heap

In a max-heap, the value of each node is greater than or equal to the values of its children. Hence, the root node contains the maximum value in the heap.

Heaps are typically used to efficiently implement priority queues, where elements with higher (or lower, depending on the type of heap) priority are removed before elements with lower (or higher) priority.

In C++, the STL provides the std::priority_queue class, which is a container adaptor that implements a max-heap by default. You can modify it to work as a min-heap by providing a custom comparator.

std::priority_queue Class in C++

• The std::priority_queue class is defined in the <queue> header.
• It is a container adaptor, which means it internally uses another container (usually a vector) to store the elements in the heap.

Important Functions of std::priority_queue:

push()

• Adds an element to the heap.
• Time Complexity: O(log n)

pop()

• Removes the top element (root) from the heap.
• Time Complexity: O(log n)

top()

• Accesses the top element (root) of the heap without removing it.
• Time Complexity: O(1)

empty()

• Checks if the heap is empty.
• Time Complexity: O(1)

Max-Heap in C++

#include <iostream>
#include <queue> // Include the <queue> header for std::priority_queue

int main() {
    std::priority_queue<int> maxHeap;

    maxHeap.push(10);
    maxHeap.push(30);
    maxHeap.push(20);

    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " "; // Output: 30 20 10
        maxHeap.pop();
    }

    return 0;
}

Min-Heap in C++

#include <iostream>
#include <queue> // Include the <queue> header for std::priority_queue

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    minHeap.push(10);
    minHeap.push(30);
    minHeap.push(20);

    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " "; // Output: 10 20 30
        minHeap.pop();
    }

    return 0;
}

In the first example, the std::priority_queue behaves as a max-heap by default. In the second example, we explicitly specify std::greater<int> as the comparator to make it behave as a min-heap.

The std::priority_queue class provides a simple and efficient way to work with heaps in C++. It abstracts away the complexities of maintaining the heap property and provides convenient functions to perform common heap operations. Whether you need a max-heap or a min-heap, the STL’s std::priority_queue has you covered.