2

優先キュー：基本操作：挿入削除（最小要素の削除）

目標：上記の機能の効率的な実行時間または成長の順序を提供すること。

優先キューの実装作成者：

Linked List: Insertion will take o(n) in case of insertion at end o(1) in case of 
             insertion at head.
             Delet (Finding minumum and Delete this ) will take o(n) 

BST:
   Insertion/Deltion of minimum = In avg case it will take o(logn) worst case 0(n)

AVL Tree: 
   Insertion/deletion/searching: o(log n) in all cases.

私の混乱はここにあります：

優先キューの実装にAVLツリーを使用したのはなぜですか、バイナリヒープを使用したのはなぜですか... AVLツリーでは、最悪の場合、o（log n）で挿入/削除/検索を実行できます。

4

3 に答える 3

3

バイナリヒープはバイナリ検索ツリー（BST）ではありません。ひどく不均衡/劣化してリストになっている場合は、実際にO（n）時間がかかります。ヒープは通常、常にO（log（n））以上です。IIRC Sedgewickは、アレイベースのヒープの平均時間がO（1）であると主張しました。

なぜAVLではないのですか？構造内で秩序を維持しすぎるためです。順序が多すぎるということは、その順序を維持するために多大な労力が費やされたことを意味します。私たちが逃げることができる順序が少なければ少ないほど良いです-それは通常より速い操作に変換されます。たとえば、RBTはAVLツリーよりも優れています。赤黒木であるRBTは、ほぼバランスの取れた木です。O（log（n））時間を確保しながら、操作を節約します。

ただし、どのツリーも完全に順序付けられた構造であるため、ヒープは一般的に優れています。これは、最小限の要素が最上位にあることを保証するだけだからです。それらは部分的にのみ注文されます。

于 2012-05-29T09:42:20.710 に答える
3

複雑さがすべてではありません。実際のパフォーマンスには他にも考慮事項があります。

ほとんどの場合、ほとんどの人は、優先キューとしては言うまでもなく、バランスの取れたツリーとしてAVLツリーを使用しません（私が見た限りでは、赤黒木がより一般的です）。

これは、AVLツリーが役に立たないということではありません。私はそれらがとても好きです。しかし、それらには比較的高価なインサートがあります。AVLツリーが適しているのは（赤黒木でさえも打ち負かす）、変更なしで多くのルックアップを実行することです。これは、優先キューに必要なものではありません。

別の考慮事項として、バイナリヒープのO（log n）挿入を気にしないでください。フィボナッチヒープには、O（1）挿入とO（log N）削除最小があります。わずかに異なるトレードオフで選択できるデータ構造がたくさんあるので、（非常に簡単な）基準を満たす最初のものを全員が選択することを期待することはできません。

于 2012-05-29T09:39:14.857 に答える
2

バイナリヒープでは、最小要素がルートであるためです。

于 2012-05-29T09:39:02.890 に答える