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

Question

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

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

我想将这些数据点存储在最大和最小堆中,但我想要用第二个值创建堆.但是,我仍然需要保留第一个值,因为我稍后在程序中使用它.我怎样才能完成这项任务？什么是最有效的STL方法总是弹出最大值或始终从一组数据点弹出最小值,同时仍然保留其他配对数据？

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