[解決済み] C++による優先度待ち行列の時間複雑性

質問

ヒープを作成するには O(n) ヒープ（または優先キュー）への挿入にかかる時間 O(log(n)) 時間です。

n 個の入力を取り、優先キューに挿入する場合、その操作の時間的複雑さはどのようになるか？ O(n) または O(n*log(n)) です。

また、ヒープ全体を空にする（つまりn回削除する）場合も同じ結果になりますよね？

解決方法は？

サイズの配列がある場合 n で、すべてのアイテムから一度にヒープを構築したい場合、Floydのアルゴリズムは、O(n)の複雑さでそれを行うことができます。参照 ヒープの構築 . に相当するものです。 std::priority_queue コンストラクタ は、コンテナ・パラメータを受け取る。

空の優先キューがあり、そこに n アイテムを一度に1つずつ処理する場合、その複雑さはO(n * log(n))です。

ですから、キューを構築する前に、キューに入るすべてのアイテムが揃っていれば、最初の方法の方が効率的です。キューを維持するために、ある期間にわたって要素を追加したり削除したりする必要がある場合は、2番目の方法、つまり項目を個別に追加する方法を使用します。

削除 n 優先度キューから項目を削除するのも、O(n * log(n))です。

のドキュメント std::priority_queue には、すべての操作の実行時の複雑さが含まれています。