CODEWITHSUNDEEP
c++stl
Bob John
Bob John

Reputation: 3878

How can I use STL to create a max and min heap for data points?

I'm trying to solve a problem that leads me to create a max and min heap for some data points. Suppose I have the following information:

(10,100)
(30,120)
(14,110)
(18,200)
(20,230)
(13,49)

And I want to store these data points in a max and min heap, but I want the heaps made by their second value. However, I still need the first value preserved as I use it later in the program. How can I accomplish this task? What are the most efficient STL methods to always pop the max or always pop the min from a set of data points, while still preserving other, paired data?

Upvotes: 3

Views: 7938

Answers (1)

Bill Lynch
Bill Lynch

Reputation: 81926

This seems straightforward:

#include <vector>
#include <algorithm>

int main() {
    std::vector<std::pair<int, int>> values = {
        {10,100},
        {30,120},
        {14,110},
        {18,200},
        {20,230},
        {13,49},
    };

    std::make_heap(values.begin(), values.end(), [](std::pair<int, int> const & lhs, std::pair<int, int> const & rhs) {
            return lhs.second < rhs.second;
            });

    // If you can't use c++11, then this is identical:
    struct {
        bool operator()(std::pair<int, int> lhs, std::pair<int, int> rhs) const {
            return lhs.second < rhs.second;
        }
    } Compare;

    std::make_heap(values.begin(), values.end(), Compare);

    // And if a priority queue works:
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(Compare)> max_heap;
    max_heap.push(std::make_pair(10,100));
    max_heap.push(std::make_pair(30,120));
    max_heap.push(std::make_pair(14,110));
    max_heap.push(std::make_pair(18,200));
    max_heap.push(std::make_pair(20,230));
    max_heap.push(std::make_pair(13,49));
}

Upvotes: 8

Related Questions