c++ - 如何使用 STL 为数据点创建最大和最小堆？

Question

我正在尝试解决一个导致我为某些数据点创建最大和最小堆的问题。假设我有以下信息：

(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?

Answer 1

这看起来很简单：

#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));
}