Heaps and Priority Queues in C++

Welcome to our exploration of the intriguing worlds of heaps and priority queues. These are powerful data structures used extensively across a range of applications, from job scheduling systems to modeling the stock market. Heaps can efficiently solve problems involving intervals, the nth largest elements, and even sorting. C++'s Standard Template Library (STL) provides a priority_queue class, offering functionality to interact with heaps efficiently.

Heaps are a category of binary trees where every parent node has a specific relationship with its children:

• In a Min-Heap, every parent node has a value less than or equal to its children.
• In a Max-Heap, every parent node has a value greater than or equal to its children.

This property allows us to repeatedly access the smallest or largest element, respectively, enabling us to solve numerous problems effortlessly. For example, if you want to find the n-th largest number in a list, using sorting can be costly. By leveraging heaps with C++, we can do this efficiently using the priority_queue.

A priority_queue in C++ is typically implemented as a Max-Heap by default, meaning the highest priority element (the largest element) is at the top. We can customize it to behave as a Min-Heap by using a comparator. Here’s an example:

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // Min-Heap

Here is how you can do it in C++:

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

std::vector<int> findKthLargestElements(const std::vector<int>& nums, int k) {
    // Min-heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    
    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    } 

    std::vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    std::reverse(result.begin(), result.end());
    return result;
}

// Test
int main() {
    std::vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;
    std::vector<int> result = findKthLargestElements(nums, k);
    
    for (int num : result) {
        std::cout << num << " ";
    }
    // Output: 6 5
    return 0;
}

Priority queues are an abstraction over heaps that store elements according to their priorities. They are used when objects need to be processed based on priority. For instance, scheduling CPU tasks based on priority is a real-life scenario for priority queues.