3

一部のデータポイントの最大ヒープと最小ヒープを作成する原因となる問題を解決しようとしています。次の情報があるとします。

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

そして、これらのデータポイントを最大ヒープと最小ヒープに格納したいのですが、2番目の値で作成されたヒープが必要です。ただし、プログラムの後半で使用するため、最初の値を保持する必要があります。どうすればこのタスクを実行できますか？他のペアのデータを保持しながら、データポイントのセットから常に最大値または最小値をポップする最も効率的なSTLメソッドは何ですか？

4

1 に答える 1

8

これは簡単に思えます：

#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));
}
于 2013-03-25T19:01:44.833 に答える