How to turn 2d array into a min heap using C++ built-in function?

Question

How can I turn this 2d array into mean heap comparing arr[i][0] with arr[i+1][0](i is the index of the array)? I tried but it's not working.

vector<vector<int>> arr = {{10, 2}, {4, 10}, {1, 4}, {11, 2}};

auto comp = [](int a, int b){
 //this function will return true if a[0] is less than b[0].
    return a[1] < b[1];
};

make_heap(arr.begin(), arr.end(), comp);

What are `i+` and `j+` supposed to mean? `++` i.e. next element, maybe? — underscore_d, Mar 24 '21 at 11:57
How do you want to compare `{10, 2}` with `{4, 10}`? What's the expected result of `{10, 2} < {4, 10}`? Do you want to compare the arrays or the elements in the inner arrays? Please provide the expected result of your code. — , Mar 24 '21 at 12:10
@jabaa Why are you even comparing `{10, 2}` with `{4, 10}` when the question states a comparison between two _elements_ of the 2-d array and not **pairs** ? — Zoso, Mar 24 '21 at 12:17
@Zoso because the lambda `fn` compares the arguments `a` and `b` and `make_heap` is called on vectors of vectors of ints. The lambda is called with two vectors as arguments. `auto fn = [](vector a, vector b)` with operator `<` for `vector` would at least solve the syntax error but probably not yield the expected result. — , Mar 24 '21 at 12:18
"I tried but it's not working." <- not a problem description. Why is it not working? What does it do? Why is that wrong? — underscore_d, Mar 24 '21 at 12:19
It seems you want to [flatten](https://stackoverflow.com/questions/6404856/generic-function-to-flatten-a-container-of-containers) the nested vector and call `make_heap` on the result. — , Mar 24 '21 at 12:24
I still don't understand whether you want a heap of integers, a heap of vectors, or a heap of pairs. Also, do you intend for the different vectors to grow and shrink? For the values to change? It may also be helpful to describe the wider scenario. — einpoklum, Mar 24 '21 at 12:30

score 1 · Answer 1 · answered Mar 24 '21 at 12:09

If I understand what you are trying to do, you can use std::priority_queue i.e:

vector<vector<int>> arr = {{10, 2, 0}, {4, 10, 1}, {1, 4, 2}, {11, 2, 1}};

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

for(const auto& i : arr)
{
    for(const auto j : i)
    {
        pq.push(j);
    }
}

while (!pq.empty())
{
    cout << pq.top() << " ";
    pq.pop();
}

Output:

0 1 1 1 2 2 2 4 4 10 10 11

score 1 · Answer 2 · 2021-03-24T12:53:48.333

First you could flatten the vector. I used the code from https://stackoverflow.com/a/6404886/15388024:

#include <iterator>
#include <algorithm>

// COCiter == Container of Containers Iterator
// Oiter == Output Iterator
template <class COCiter, class Oiter>
void flatten (COCiter start, COCiter end, Oiter dest) {
    while (start != end) {
        dest = std::copy(start->begin(), start->end(), dest);
        ++start;
    }
}

Then you can apply make_heap with your comparison:

vector<vector<int>> arr = {{10, 2}, {4, 10}, {1, 4}, {11, 2}};
vector<int> flatArr;
flatten(arr.begin(), arr.end(), std::back_inserter(flatArr));

auto fn = [](int a, int b){
    return a < b;
};

make_heap(flatArr.begin(), flatArr.end(), fn);

An example:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

template <class COCiter, class Oiter>
void flatten (COCiter start, COCiter end, Oiter dest) {
    while (start != end) {
        dest = std::copy(start->begin(), start->end(), dest);
        ++start;
    }
}

int main() {
    std::vector<std::vector<int>> arr = {{10, 2}, {4, 10}, {1, 4}, {11, 2}};
    std::vector<int> flatArr;
    flatten(arr.begin(), arr.end(), std::back_inserter(flatArr));

    auto fn = [](int a, int b){
        return a > b;
    };

    std::make_heap(flatArr.begin(), flatArr.end(), fn);
    
    for (const auto el : flatArr) {
        std::cout << el << ' ';
    }
}

with output:

11 10 10 2 1 4 4 2 // with heap property flatArr[(i + 1) / 2 - 1] >= flatArr[i]

//       11
//      /  \
//    10    10
//    /\    /\
//   2  1  4  4
//  /
// 2

Change the comparison function to

auto fn = [](int a, int b){
    return a > b;
};

to get a min heap

1 2 4 2 10 4 11 10 // with min heap property flatArr[(i + 1) / 2 - 1] <= flatArr[i]

//        1
//      /   \
//     2     4 
//    / \   / \
//   2  10 4  11
//  /
// 10

How to turn 2d array into a min heap using C++ built-in function?

2 Answers2