10

私はヒープに関するいくつかの宿題に取り組んでおり、ヒープがどのように構造化されているかを理解しています。ヒープには、ヒープ プロパティを満たす各ノードが必要です。

max-heap プロパティは、ルート以外のすべてのノード i について、Heap[Parent(i)] >= Heap[i] です。

したがって、各ノードでは、上位のノードほど数値が高くなり、下位のノードほど数値が低くなります。これは分かります。しかし、リスト内の最大のn個の数値を単純に取得する以外にヒープを使用する方法は見当たりません。特定の値を検索してノードを返したり、(最大ヒープ内で) n 個の最小値を検索したりする簡単な方法がわかりません。どちらも、二分探索木では比較的簡単です。

単純な二分探索木を使用しないのはなぜですか? それとも、バランスの取れた二分探索木ですか?

編集：これは宿題の問題に対する答えを探しているわけではないことに注意してください。実際の課題は、insert() 関数と extractMax() 関数の並列 p ヒープの疑似コードを作成することでした。そして、私はすでにそれらに答えました。彼らは私がヒープを本当に理解していないことに気づきました。

4

2 に答える 2

13

ヒープ データ構造には多くの用途があります。

  • ヒープソート: 最適な並べ替え方法の 1 つで、二次的な最悪のシナリオはありません。
  • 選択アルゴリズム: ヒープを使用して、最小値、最大値、最小値と最大値の両方、中央値、さらには k 番目に大きい要素を見つけることを線形時間 (多くの場合一定時間) で実行できます。[4]
  • グラフ アルゴリズム: ヒープを内部トラバーサル データ構造として使用することにより、多項式の順序で実行時間が短縮されます。このような問題の例としては、Prim の最小スパニング ツリー アルゴリズムと Dijkstra の最短経路問題があります。

完全またはほぼ完全なバイナリ ヒープは、配列のみを使用して非常に効率的な方法で表すことができます。最初 (または最後) の要素にはルートが含まれます。配列の次の 2 つの要素には、その子が含まれます。次の 4 つは、2 つの子ノードの 4 つの子を含みます。したがって、位置 n にあるノードの子は、1 ベースの配列では位置 2n と 2n+1、または配列では位置 2n+1 と 2n+2 になります。ゼロから始まる配列。これにより、単純なインデックス計算を行うことで、ツリーを上下に移動できます。ヒープのバランスは、順序が乱れた要素を交換することによって行われます。余分なメモリを必要とせずに配列からヒープを構築できるため (ノードなど)、ヒープソートを使用して配列をその場で並べ替えることができます。

一部のアプリケーションでのツリーに対するヒープのもう 1 つの利点は、Tarjan のアルゴリズムを使用してヒープの構築を線形時間で実行できることです。

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

于 2011-03-08T12:28:07.587 に答える
6

ポインターがないため (通常、ヒープは配列ベースのデータ構造を使用します)、操作はバイナリ ツリーよりも高速になる傾向があります。また、一部のより複雑なヒープ (二項など) は効率的にマージできますが、これはバイナリ ツリーでは容易ではありません。この SO questionにも情報があります。

于 2011-03-08T03:35:03.477 に答える