C ++標準ライブラリのドキュメントでいくつかの関数を検索しているときに、優先キューのプッシュとポップには一定の時間が必要であることを読みました。
http://www.cplusplus.com/reference/stl/priority_queue/push/
定数（priority_queue内）。ただし、push_heapは対数時間で動作することに注意してください。
私の質問は、プッシュとポップのためにO（1）で優先キューを維持するためにどのようなデータ構造が使用されているかということです。
cplusplus.com のページを参照していると思います。
ページの前半で、次のように述べています。
このメンバー関数は、基になるコンテナー オブジェクトのメンバー関数 push_back を効果的に呼び出し、次に push_heap アルゴリズムを呼び出して、priority_queues のヒープ プロパティを保持します。
そのため、O(1)プッシュ後、データ構造はそのヒープ プロパティの不変を失い、そのプロパティを復元するための呼び出しで常にそれに続きます。O(log N)つまり、O(1)操作は操作全体の一部にすぎません。完全な操作はO(1) + O(log N)と同じO(log N)です。
彼らが言及している理由は、優先度キューがアダプターであり、基になるコンテナーの機能とアダプターの機能の違いを強調しようとしているからだと思います。
priority_queueの基盤となるストレージは、ベクトル、deque、またはランダムアクセスイテレータをサポートする同様のものにすることができます。ストレージはヒープとして維持されますが、これはプッシュ用のO（N）ではないため、これを間違って読んだと思われます
プッシュとポップは、に従って対数時間で実行されます
私はO（1）の主張に懐疑的です...どこでそれを見ましたか？
いずれにせよ、ここにgccの優先キューの実装に関するいくつかの注意があります。
そのような種類のヒープはありません。彼らは、対数であるpush_heapを呼び出すので、lognであると書いています。
push_heapこの規格では、これらのメンバーをとで定義していpop_heapます。これは、コンパイル可能性を意味します。
その参照が真実である（それはまた一定であると言うtop）場合、なぜ誰もがを使用して汎用O（N）ソートを実装しないのstd::priority_queueですか？
第二に、これは、非常に誤解を招くような方法で、参照が言おうとしていることです。複雑さは、push_backO（1）+ push_heap（O（log N））の複雑さです。