最近、私はここにスタックオーバーフローに関する質問を投稿しましたマルチマップの時間計算量の問題 そして、私はヒープの使用について言及するいくつかの素晴らしい回答を得ましたが、奇妙なことに、これまでまったく使用していませんでした。minheapとmaxheapを使って書き直した新しいプログラムを作成しました。この問題のために私が実装した他のどのプログラムよりもはるかに高速であるという点で、それはうまく機能しました。唯一の問題は、時々間違った答えを投げることでした。私は戻ってたくさんのデバッグをしました。問題はヒープの編成にあることに気づきました。比較演算でpush_heapとpop_heapを使用した場合のように、ソートおよび配布されていませんでした。また、Visual Studioでプログラムを実行しようとすると、多くのアサーションエラーがスローされてしまいます。私はcplusplus.comとcppreference.comでヒープとそのメソッドについてもっと読んでみました。
私を混乱させる最初のことはpush_heapです。私が理解している方法は次のとおりです。push_heapには2つの引数があり、デフォルトでは最小値を最後の1の位置にプッシュします。これは、最初の引数が2番目の引数よりも小さい場合にのみ実行され、それ以外の場合は同じままです。基本的に、通常のヒープの順序を維持します。3番目のオプションの引数は比較演算子です。これはgreater（）として使用でき、greater要素を最後の1の位置にプッシュします。
意味をなさないのは、ベクトル内で数値の動的な挿入または削除が行われている場合、この順序を維持するのに問題があるということです。ベクトルを昇順にしたい場合は、より大きな操作を使用してヒープをプッシュし続け、値が昇順になるようにします。ただし、push_heapメソッドを最初に見ると混乱します。これは、たとえば次のような数値の範囲で実行される他のアルゴリズム関数のいくつかとよく似ているためです。
std::unique (myvector.begin(), myvector.end(), myfunction);
push_heapは実行しません。最初は理解できなかった、ベクトルの範囲内のすべての数値に対してこの比較演算を実行するわけではありません。
push_heapが実際にベクトルをソートし続けていないことを発見した後、バイナリ検索を使用するためにベクトルをソートし続ける必要がありました。sort_heapを使用しましたが、プログラムの速度が低下し、十分な速度が得られませんでした。
また、奇妙な場合にpush_heapが無効なヒープエラーをスローすることがあります。
たとえば：
push_heap(v.begin(), v.end(), greater<int>());
ベクトルが755、98、55、22の場合
push_heapの後に表示されます：
22, 98, 55, 755
しかし、あなたが22、98、55、755を持っていたとしましょう
通常、比較で誤ったリターンが発生するため、プッシュを実行せずに先に進みます。これは予想されることです。
しかし時々私はpush_heapを試してみます：
887、52、44、22
そしてそれは言うでしょう
'invalid heap'
または私が試してみると： 22、52、44、887、単にfalseを返し、その上に移動する代わりに、
'invalid heap'
これは、pop_heapでも発生することがあります。
なぜ無効なヒープを取得するのですか？すべてのヒープが降順である必要があるためですか？
編集：私はcplusplus.comでこれを見つけました、それは私が1つの質問に答えると思います：
The element with the highest value is always pointed by first. The order of the other elements depends on the particular implementation, but it is consistent throughout all heap-related functions of this header.