C++最大ヒープ最小ヒープとpush_heap pop_heap

make_Heap:異なるパラメータに基づいて大きなスタックまたは小さなスタックを生成し、デフォルトでは大きなスタックを生成します.make_heap(_RAITter,_RAITter)デフォルトでは、大きなスタックmake_が生成されます.heap(_RAIter,_RAIter,_Compare) _Compareには2つのパラメータがあります.1つはgreater(小さなトップスタックを生成する)です.1つはless(大きなトップスタックを生成する)push_heap()です.スタックに要素を挿入し、スタックのルールを確立します.
push_heap(_RAitter,_RAitter)デフォルトは大頂山push_heap(_RAIter,_RAIter,_Compare) _Compareには2つのパラメータがあり、1つはgreater(小さなトップスタック)、1つはlessです(大屋根ヒープ)push_heapを呼び出す前にmake_heapを呼び出す必要があります.まず、push_back挿入要素のヒープを作成し、次にpush_heapを呼び出す必要があります.これにより、最後の要素が適切な位置に挿入されます.push_heapの_Compareとmake_heapの_Compareパラメータが一致しなければなりません.そうしないと、ヒープの挿入に失敗します.最後の要素は最後の位置にあります.挿入に失敗しました
pop_Heap()はスタックに基づいて、スタックトップ要素をポップアップします.pop_heap(_RAitter,_RAitter)デフォルトは大頂山pop_heap(_RAIter,_RAIter,_Compare) _Compareには2つのパラメータがあり、1つはgreater(小さなトップスタック)、1つはless(大きなトップスタック)、例えばpop_heap(nums.begin()、nums.end()greater()は、スタックトップ要素(配列の最初の位置)と配列の最後の位置を合わせます.その後、配列pop_backを呼び出して、この要素を削除できます.pop_heapの_Compareとmake_heapの_Compareパラメータは一致しなければなりません.そうしないと失敗します.
例:データ・ストリームの中位数をどのように取得しますか?データストリームから奇数個の数値を読み出すと、中位数は、すべての数値がソートされた後に中間に位置する数値である.データストリームから偶数個の数値が読み出されると、中位数は、すべての数値が並べ替えられた後の中間の2つの数の平均値となります.

class Solution {
    vector min, max; // as heap
public:
    void Insert(int num) {
        if (((min.size() + max.size()) & 0x1) == 0) {
            if (max.size() > 0 && num < max[0]) {
                max.push_back(num);
                push_heap(max.begin(), max.end(), less());
                num = max[0];
                pop_heap(max.begin(), max.end(), less());
                max.pop_back();
            }
            min.push_back(num);
            push_heap(min.begin(), min.end(), greater());
        } else {
            if (min.size() > 0 && num > min[0]) {
                min.push_back(num);
                push_heap(min.begin(), min.end(), greater());
                num = min[0];
                pop_heap(min.begin(), min.end(), greater());
                min.pop_back();
            }
            max.push_back(num);
            push_heap(max.begin(), max.end(), less());
        }
    }

    double GetMedian() {
        if (min.size() + max.size() == 0) return 0; // Error

        if (((min.size() + max.size()) & 0x1) == 0) {
            return ((double)min[0] + (double)max[0]) * 0.5;
        } else {
            return (double)min[0];
        }
    }
};