最大ヒープとバランスの取れたBSTを使用した優先キューの実装

Jan 25 2021

バランスの取れたBSTと最大ヒープの両方がで挿入と削除を実行しO(logn)ます。ただし、最大ヒープで最大値を見つけることは重要ですO(1)が、これはO(logn)バランスの取れたBSTです。

最大ヒープ内の最大値を削除するO(logn)と、削除操作であるためにかかります。

平衡BSTでは、最大要素の削除=最大値の検索+削除; logn + lognはに減少しO(logn)ます。したがって、平衡BSTの最大値を削除してもO(logn)。

最大ヒープのそのようなアプリケーションの1つは優先キューであり、その主な目的はすべてのデキュー操作の最大値を削除することです。最大要素の削除が最大O(logn)ヒープと平衡BSTの両方に対するものである場合、次の質問があります

常に複雑さは最悪の場合について計算されます。どんな助けでも大歓迎です。

回答

2 trincot Jan 25 2021 at 20:05

完全に検索可能なバランスの取れたBSTを使用するのではなく、実装が簡単であるという理由だけで、優先キューの最大ヒープの目的は何ですか？

ヒープのいくつかの利点は次のとおりです。

ソートされていない入力配列が与えられた場合でも、ヒープはO（n）時間で構築できますが、BSTにはO（nlogn）時間が必要です。
初期入力が配列の場合、同じ配列をヒープとして使用できます。つまり、追加のメモリは必要ありません。配列内のインプレースデータを使用してBSTを作成する方法を考えることはできますが、それは（プリミティブ型の場合）非常に奇妙であり、処理のオーバーヘッドが大きくなります。BSTは通常、最初から作成され、作成時にデータをノードにコピーします。

興味深い事実：ソートされた配列もヒープであるため、入力がソートされていることがわかっている場合は、ヒープを構築するために何もする必要はありません。
ヒープは相互参照を格納する必要なしに配列として格納できますが、BSTは通常、左右の参照を持つノードで構成されます。これには少なくとも2つの結果があります。
- BSTに使用されるメモリは、ヒープの約3倍です。
- いくつかの操作はヒープとBSTの両方で同じ時間計算量を持ちますが、BSTを適応させるためのオーバーヘッドははるかに大きいため、これらの操作に費やされる実際の時間はBSTの場合の（一定の）係数です。

平衡係数の計算がないので、最大ヒープは不平衡二分木と呼ぶことができますか？

ヒープは実際には完全な二分木であるため、常に可能な限りバランスが取れています。リーフは常に最後または最後の1つのレベルに配置されます。自己平衡BST（AVL、赤黒など）は、3レベル以上で葉が発生することが多い、その高レベルの平衡に勝るものはありません。

すべての平衡BSTは優先キューとして使用でき、O（logn）でも検索できますが、最大ヒープ検索はO（n）で正しいですか？

はい、その通りです。したがって、アプリケーションに検索機能が必要な場合は、BSTの方が優れています。

2 SerejaBogolubov Jan 25 2021 at 16:53

完全に検索可能なバランスの取れたBSTを使用するのではなく、実装が簡単であるという理由だけで、優先キューの最大ヒープの目的は何ですか？

いいえ。最大ヒープは、O（1）時間で次の（優先度を尊重する）要素をできるだけ早く返すように注意深く計測されているため、より適切に適合します。これが、可能な限り単純な優先度付きキューに求められるものです。

平衡係数の計算がないので、最大ヒープは不平衡二分木と呼ぶことができますか？

いいえ。バランスもあります。簡単に言うと、ヒープのバランス調整は、シフトアップまたはシフトダウン操作（順序が正しくない要素の交換）によって行われます。

すべての平衡BSTは優先キューとして使用でき、O（logn）でも検索できますが、最大ヒープ検索はO（n）で正しいですか？

うん！リンクリストだけでなく、配列を使用することもできます。O表記の点でより高価になり、練習がはるかに遅くなります。