これら2つは非常によく似ており、構造はほぼ同じです。違いは何ですか？それぞれの異なる操作の時間計算量は何ですか？
回答
ヒープは、上位レベルの要素が下位レベルの要素よりも大きい（max-heapの場合）または小さい（min-heapの場合）ことを保証しますが、BSTは順序（「左」から「右」）を保証します。 。並べ替えられた要素が必要な場合は、BSTを使用します。 Danteはオタクではありません
ヒープはfindMin / findMax（O（ 1））、BSTはすべての検索（O（logN））で良好ですが、挿入は両方の構造でO（logN）です。findMin/ findMax（優先度関連など）のみを気にする場合は、ヒープを使用してください。すべてを並べ替えて、BSTを使用します。
コメント
- findMinでBSTの方が優れていると思います& findMax stackoverflow .com / a / 27074221/764592
- これは単なる通信だと思います誤解について。二分木は、Yeoが指す最小値と最大値を見つけるように簡単に変更できます。これは実際にはヒープの制限です。のみの効率的な検索は最小または最大です。ヒープの真の利点は、私が説明するように O（1）平均挿入です： stackoverflow.com/a/29548834/895245
- このビデオによると、大きい方が下のレベルの子孫でない限り、下のレベルで大きい値を持つことができます。
- ヒープはルートからリーフにソートされ、BSTは左から右にソートされます。
- 一定時間で中央値を見つけ、対数時間で中央値を削除したい場合はどうすればよいですか？どのデータ構造を選択する必要がありますか？ MinHeapの実装は機能しますか？提案してください。
回答
概要
Type BST (*) Heap Insert average log(n) 1 Insert worst log(n) log(n) or n (***) Find any worst log(n) n Find max worst 1 (**) 1 Create worst n log(n) n Delete worst log(n) log(n) このテーブルのすべての平均時間は、挿入を除いて最悪の時間と同じです。
-
*：この回答のどこでも、BST ==バランスの取れたBSTです。これは、アンバランスが漸近的に吸うためです -
**：この回答で説明されている簡単な変更を使用する -
***：ポインタツリーヒープのlog(n)、n動的配列ヒープの場合
BSTよりもバイナリヒープの利点
-
バイナリヒープへの平均挿入時間は
O(1)であり、BSTは。 このはヒープのキラー機能です。O(1)はフィボナッチヒープのように（より強く）償却され、最悪の場合は Brodal queue 。ただし、非漸近的なパフォーマンスのために実用的ではない場合があります： https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere -
バイナリヒープは、動的配列またはポインタベースのツリー（BSTのみ）の上に効率的に実装できます。ポインタベースのツリー。したがって、ヒープのサイズ変更の待ち時間をときどき許容できる場合は、よりスペース効率の高い配列実装を選択できます。
-
バイナリヒープの作成は
O(n)ワーストケース、O(n log(n))はBSTです。
バイナリヒープに対するBSTの利点
-
任意の要素の検索は
O(log(n))。 このはBSTのキラー機能です。ヒープの場合、一般的に、最大の要素である
O(1)を除きます。
BSTに対するヒープの「誤った」利点
-
ヒープは
O(1)で、最大BSTO(log(n))を検索します。これこれはよくある誤解です。BSTを変更して最大の要素を追跡し、その要素が変更される可能性がある場合はいつでも更新するのは簡単だからです。大きなスワップを挿入すると、削除すると2番目に大きい要素が見つかります。 https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation （Yeoがと言及）。
実際、これはBSTと比較したヒープの制限です。唯一の効率的な検索は、最大の要素の検索です。
平均的なバイナリヒープ挿入はO(1)
出典：
- 紙： http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
- WSUスライド： http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf
直感的な議論：
- 最下位のツリーレベルには最上位レベルよりも指数関数的に多くの要素があるため、新しい要素はほぼ確実に最下位に配置されます
- ヒープ挿入下から開始、BSTは上から開始する必要があります
バイナリヒープでは、特定のインデックスで値を増やすことも必要です同じ理由でO(1)。ただし、それを実行したい場合は、ヒープ操作で追加のインデックスを最新の状態に保ちたいと思う可能性があります https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu 例ダイクストラのために。追加の時間コストなしで可能です。
実際のハードウェアでのGCCC ++標準ライブラリ挿入ベンチマーク
C ++ std::set（赤黒ツリーBST ）と（動的配列ヒープ）挿入して、挿入時間が正しいかどうかを確認します。これが私が得たものです：
- ベンチマークコード
- プロットスクリプト
- プロットデータ
- CPUを搭載したLenovoThinkPadP51ラップトップのUbuntu19.04、GCC 8.3.0でテスト済み：Intel Core i7-7820HQ CPU（4コア/ 8スレッド、2.90 GHzベース、8 MBキャッシュ）、RAM：2x Samsung M471A2K43BB1-CRC（2x 16GiB、2400 Mbps）、SSD：Samsung MZVLB512HAJQ-000L7（512GB、3,000 MB / s）
はっきりと：
-
ヒープ挿入t imeは基本的に一定です。
動的配列のサイズ変更ポイントをはっきりと確認できます。 1万回の挿入ごとに平均化して、システムノイズを超えるものをすべて表示できるようにしているため、これらのピークは実際には表示されているものの約1万倍です！
ズームされたグラフは、基本的に配列のサイズ変更ポイントのみを除外し、ほとんどすべての挿入が25ナノ秒未満であることを示しています。
-
BSTは対数です。すべての挿入は、平均的なヒープ挿入よりもはるかに低速です。
-
BSTとハッシュマップの詳細な分析： https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119
gem5
gem5 は完全なシステムシミュレータであるため、m5 dumpstats。そこで、これを使用して個々の挿入のタイミングを推定しようとしました。
解釈：
-
ヒープは一定ですが、数行あり、上位の各行がよりまばらになっていることが詳細にわかります。 。
これは、より高い挿入に対して行われるメモリアクセスの待ち時間に対応している必要があります。
-
TODO実際にはBSTを完全に解釈することはできません。はそれほど対数的には見えず、やや一定です。
この詳細を使用すると、いくつかの明確な線も表示されますが、それらが何を表しているのかわかりません。上下を挿入するので、薄くしますか？
aarch64 ivにこのビルドルート設定でベンチマークしますid = “635e322f0e”>
HPI CPU 。
BSTをアレイに効率的に実装できません
ヒープ操作は単一のツリーブランチを上下にバブルするだけでよいため、O(log(n))最悪の場合のスワップ、O(1)平均。
BSTのバランスを保つには、ツリーの回転が必要です。これにより、最上位の要素が別の要素に変更される可能性があり、配列全体を移動する必要があります（O(n)）。
ヒープは配列に効率的に実装できます
親と子のインデックスは現在のインデックスから計算できますここに示すように。
BSTのようなバランシング操作はありません。
最小値の削除は、最も心配な操作です。トップダウンである必要があります。ただし、ここで説明するように、ヒープの1つのブランチを「パーコレーション」することでいつでも実行できます。ヒープは常にバランスが取れているため、これはO（log（n））の最悪のケースにつながります。
削除するノードごとに1つのノードを挿入すると、漸近線の利点が失われます。 O（1）削除が支配的であるため、ヒープが提供する平均挿入。BSTを使用することもできます。ただし、ダイクストラは削除ごとにノードを数回更新するため、問題ありません。
動的配列ヒープとポインタツリーヒープ
ヒープは効率的に実装できますポインタヒープの上： https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations
動的配列の実装はスペース効率が高くなります。各ヒープ要素にstructへのポインタのみが含まれているとします。
-
ツリーの実装では、要素ごとに3つのポインタを格納する必要があります。左の子と右の子。したがって、メモリ使用量は常に
4n（3つのツリーポインタ+ 1つのstructポインタ）です。ツリーBSTもさらにバランス情報が必要です。黒赤さ。
-
動的配列の実装は、2倍にした直後のサイズが
2nになる可能性があります。したがって、平均すると1.5nになります。
一方、ツリーヒープには、最悪の場合の挿入が適しています。バッキング動的配列をコピーしてそのサイズを2倍にすると、O(n)最悪の場合が発生しますが、ツリーヒープはノードごとに新しい小さな割り当てを行うだけです。
それでも、バッキングはアレイのダブリングはO(1)で償却されるため、最大レイテンシを考慮する必要があります。 ここで言及。
哲学
-
BSTは、親とすべての子孫の間のグローバルプロパティを維持します（左が小さく、右が大きい）。
BSTの最上位ノードは中央の要素です。 、維持するにはグローバルな知識が必要です（小さい要素と大きい要素がいくつあるかを知っています）。
このグローバルプロパティは維持するのに費用がかかりますが（log n insert）、より強力な検索を提供します（log n search） 。
-
ヒープは、親子と直接の子（親>子）の間のローカルプロパティを維持します。
ヒープのトップノートは、大きな要素です。維持するために地元の知識だけが必要です（あなたの親を知っています）。
BSTとヒープとハッシュマップの比較：
-
BST：どちらかが妥当です：
-
ヒープ：単なるソートマシンです。最小/最大要素のみを高速でチェックできるため、効率的な順序付けされていないセットにすることはできません。
-
ハッシュマップ：順序付けされていないセットのみにすることができ、効率的な並べ替えマシンではありません。ハッシュによって順序が混同されるためです。
二重リンクリスト
二重にリンクされたリストは、最初のアイテムが最も優先されるヒープのサブセットと見なすことができるので、ここでもそれらを比較してみましょう：
- 挿入：
- 位置：
- 二重リンクリスト：挿入されたアイテムは、最初または最後のいずれかである必要があります。これらの要素へのポインタしかないためです。
- バイナリヒープ：挿入されたアイテムリンクリストよりも制限が少なくなります。
- 時間：
- 二重リンクリスト：
O(1)アイテムへのポインタがあり、更新が非常に簡単であるため、最悪のケース - バイナリヒープ：
O(1)平均、したがってリンクリストよりも悪い。より一般的な挿入位置があります。
- 二重リンクリスト：
- 位置：
- 検索：
O(n)両方を検索
このユースケースは、ヒープのキーが現在のタイムスタンプである場合です。その場合、新しいエントリは常にリストの先頭に移動します。したがって、正確なタイムスタンプを完全に忘れて、リスト内の位置を優先度として保持することもできます。
これを使用して、 LRUキャッシュを実装できます。 。ダイクストラのようなヒープアプリケーションのと同様に、キーからリストの対応するノードへの追加のハッシュマップを保持して、どのノードをすばやく更新するかを見つける必要があります。 。
さまざまなバランスBSTの比較
ただし、漸近的な挿入と検索これまでに見た「平衡BST」として一般的に分類されるすべてのデータ構造の時間は同じであり、BBSTが異なればトレードオフも異なります。これについてはまだ十分に研究していませんが、要約するとよいでしょう。これらのトレードオフは次のとおりです：
- 赤黒の木。 2019年の時点で最も一般的に使用されているBBSTのようです。これは、GCC 8.3.0 C ++実装で使用されるものです
- AVLツリー。 BSTよりも少しバランスが取れているように見えるので、検索の待ち時間が少し長くなりますが、検索の待ち時間が長くなる可能性があります。Wikiの要約：「AVLツリーは、同じ操作セットをサポートし、基本的な操作に[同じ]時間がかかるため、赤黒木と比較されることがよくあります。ルックアップを多用するアプリケーションの場合、AVLツリーは赤黒木よりも高速です。それらはより厳密にバランスが取れています。赤黒木と同様に、AVLツリーは高さのバランスが取れています。一般に、どちらのミューも重量バランスもミューバランスもありません< 1 / 2;つまり、兄弟ノードの子孫の数は大きく異なる可能性があります。 “
- WAVL 。 元の論文では、リバランスとローテーション操作の限界という点で、このバージョンの利点について説明しています。
関連項目
CSに関する同様の質問：内容’バイナリ検索ツリーとバイナリヒープの違いは？
コメント
- すばらしい答え。ヒープの一般的なアプリケーションは、中央値、k min、上位k要素です。これらの最も一般的な操作では、minを削除してから挿入します（通常、純粋な挿入操作がほとんどない小さなヒープがあります）。したがって、実際には、これらのアルゴリズムではBSTを上回らないようです。
- 例外的な回答!!!基礎となるヒープ構造としてdequeを使用することで、サイズ変更時間を大幅に短縮できますが、チャンクへのポインターの（より小さな）配列を再割り当てする必要があるため、O（n）の最悪のケースです。
回答
ヒープでは、ノードが子よりも優先される必要があります。最大ヒープでは、各ノードの子はそれ自体よりも小さい必要があります。これは、最小ヒープの場合は逆です。
二分探索木（BST）は、兄弟ノード間の特定の順序（pre-order、in-order、post-order）に従います。ツリーはは、ヒープとは異なり、並べ替えられます：
BSTの平均は $ O（\ log n）$ 。
バイナリヒープの平均
コメント
- @FrankW抽出は$ O（\ log n）$です、いいえ？
回答
データ構造では、懸念のレベルを区別する必要があります。
-
このqの抽象的なデータ構造（格納されているオブジェクトとその操作） uestionは異なります。 1つは優先キューを実装し、もう1つはセットを実装します。優先度付きキューは、任意の要素を見つけることには関心がなく、最も優先度の高い要素のみを見つけます。
-
構造の具体的な実装。ここで一見すると、両方とも（二分）木ですが、構造特性は異なります。キーの相対的な順序と可能なグローバル構造の両方が異なります。 （
BSTでは、キーは左から右に並べられ、ヒープでは上から下に並べられます。）IPlantが正しく述べているように、ヒープも「完全」である必要があります。 。 -
低レベルの実装には最終的な違いがあります。 （不均衡な）二分探索木には、ポインターを使用した標準的な実装があります。反対に、バイナリヒープには、配列を使用した効率的な実装があります（正確には構造が制限されているため）。
回答
前の回答に加えて、ヒープにはヒープ構造プロパティが必要です;ツリーはいっぱいである必要があり、常にいっぱいであるとは限らない最下層は、ギャップなしで左端から右端まで埋める必要があります。