c++ - 如何使用 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));
}