Example: Min-Heap Print Sorted Matrix Elements in C++

// Min-Heap Print Sorted Matrix Elements
#include <iostream>
#include <vector>
#include <queue> // For std::priority_queue

// Structure to hold element value, its row, and column index
struct Element {
    int value;
    int row;
    int col;

    // Custom comparator for min-heap (smallest value on top)
    bool operator>(const Element& other) const {
        return value > other.value;
    }
};

int main() {
    // Step 1: Define the matrix
    std::vector<std::vector<int>> matrix = {
        {10, 20, 30, 40},
        {15, 25, 35, 45},
        {27, 29, 37, 48},
        {32, 33, 39, 50}
    };

    int R = matrix.size();
    if (R == 0) {
        std::cout << "Matrix is empty." << std::endl;
        return 0;
    }
    int C = matrix[0].size();
    if (C == 0) {
        std::cout << "Matrix rows are empty." << std::endl;
        return 0;
    }

    // Step 2: Create a min-priority queue (min-heap)
    // The Element struct's operator> defines the min-heap behavior
    std::priority_queue<Element, std::vector<Element>, std::greater<Element>> minHeap;

    // Step 3: Push the first element of each row into the min-heap
    // along with its row and column index
    for (int i = 0; i < R; ++i) {
        minHeap.push({matrix[i][0], i, 0});
    }

    // Step 4: Extract elements from the heap and add next from same row
    std::cout << "Sorted elements (Min-Heap):" << std::endl;
    while (!minHeap.empty()) {
        // Get the smallest element from the heap
        Element current = minHeap.top();
        minHeap.pop();

        // Print the element
        std::cout << current.value << " ";

        // If there's a next element in the same row, push it to the heap
        if (current.col + 1 < C) {
            minHeap.push({matrix[current.row][current.col + 1], current.row, current.col + 1});
        }
    }
    std::cout << std::endl;

    return 0;
}