ソートされた基になるコンテナの場合、優先キューの作成にO（nlogn）時間がかかるのに、ソートされていない基になるコンテナの場合、作成にO（n）時間しかかからないのはなぜですか。また、なぜ（ソートされた場合）優先キューをソートするのにO（nlogn）がかかるのですか？
どちらの場合でも、実行時間を理解するのに役立つ図はありますか？このような場合、ヒープを使用する方が速いですか？
質問する
402 次
2 に答える
0
プライオリティ キューは、max-heap を使用して実装できます。実際、最大ヒープは、優先キューの漸近的に最適な実装を提供します。したがって、ソートされていないコンテナの場合、優先キューを作成するには、n 個の要素からヒープを作成するだけで済みます。これは、Heapify アルゴリズムを使用して O(n) 時間で実行できます。ソートされた場合、Theta(n) バウンドであることがわかっている要素を完全にソートする必要があります。
于 2013-02-13T11:34:03.877 に答える
0
プライオリティ キューを実装する唯一の方法がないため、一般的にはあなたの質問に答えることはできないと思います。
それはむしろ、実行できる操作によって定義され、それを実装する方法はたくさんあります。ヒープや AVL ツリーなど、いくつかの可能性があります。
この質問に答えるには、使用している STL 実装によって選択された実装を調べる必要があります。
SGI 実装のドキュメントには次のように書かれています。
[2] この制限が、priority_queue が存在する唯一の理由です。要素の繰り返しが重要な場合は、ソートされた順序で維持されるベクトル、セット、または make_heap、push_heap、および pop_heap を使用してヒープとして維持されるベクトルを使用できます。実際、Priority_queue は、ヒープとして維持されるランダム アクセス コンテナーとして実装されます。ヒープ操作を手動で実行する代わりにコンテナー アダプター priority_queue を使用する唯一の理由は、ヒープの不変条件に違反する可能性のある操作を決して実行しないことを明確にするためです。
したがって、あなたが提案したようにヒープを使用しているようです。
于 2013-02-13T11:36:29.880 に答える