data-structures - 優先キューの時間ですか？

Question

• プライオリティ リストが n ノードのリストを作成するのにかかる時間は? 上記の時間内にこれをどのように達成しますか？

• delete-min関数 (最小の要素を取得してリストから削除する) にはどのくらいの時間がかかりますか? 上記の時間内にこれをどのように達成しますか？

Answer 1

プライオリティ キューの作成方法によって異なります。ヒープ構造を使用している場合、プライオリティ キューを構築するには nlogn が必要です。O(N) でも最小ヒープを構築できる方法を覚えています。詳細については、CLRS を参照してください。

ヒープ構造を調べて、ヒープ構造を構築する方法を見つけます。基本的に、コンパレーターはノードの優先度になります。

delete-min は O(logn) かかります。ヒープデータ構造をもう一度見てください。

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

プライオリティ キューにリンク リストを使用することもできます。リンクされたリストでは、delete min も定数になります。ただし、ビルド優先度キューは、入力によっては O(N^2) まで上がる場合があります。