メモリ管理におけるヒープはプールに似ています。 があるStackOverflow でのディスカッション、この違いの詳細については話しません。アルゴリズムにおけるヒープの概念について話しているのはご存知のとおり、データ構造だけで十分です。私たちは今もそのスタイルを守り続けていますアルゴリズムの概要。ヒープは、配列で表される完全なバイナリ ツリーです。バイナリ ツリーはツリーの一種であり、すべての親ノードには最大 2 つの子があり、それらを左サブツリーと右サブツリーと呼びます。
完全な二分木とは、層数が k で、層数が 2 のときの二分木です。k
-1 ノード。このような：そして、完全なバイナリ ツリーは、完全なバイナリ ツリー リークであるか、いくつかのノードが欠けていないが、上から下、左から右にノードを満たしている必要があると考えることができます。
これは、右からいくつかのノードのみが欠如できることを意味します。このような：
ヒープを使用してこの完全なバイナリ ツリーを保存する場合、[A、B、C、D、E、F、G、H、I、J、K、L] のような配列として保存できます。この保存方法を使用すると、このツリーのルートのインデックスが 1 であることがわかります。
そして、すべての親ノードのインデックスは、子ノードのインデックスを 2 で割ったものです。また、左のサブノードのインデックスは、その親ノードのインデックスに 2 を乗じたものとなり、右のサブノードのインデックスはその親になりますノードのインデックスは 2 を乗算してから 1 を加算します。
したがって、子ノードと親ノードにアクセスする関数を取得します。
次に、データ構造である Max-Heap について説明します。それは山であり、どの親もその子よりも大きいです。したがって、Max-Heap ではルートが最大の数値であることがわかります。画像は Max-Heap とそれに対応する配列です。
Min-Heap は簡単に定義できますが、ここでは説明しません。
のノードの場合、最大ヒープサブノードより小さい場合、最大ヒープの規則に違反します。そのサブノードが有効な最大ヒープであることがわかっている場合は、次の方法でそれを修正できます。最大ヒープ化手術。手順としては、このノードとその子の値を比較し、誰が最大であるか、親ノードでない場合は、最大のサブノードを親ノードと交換します。次に、その子を持つサブノードを調べます。段階的に、操作後に最大ヒープが有効になることが確認できます。
ビデオデモを作成します。4 はエラーノードです。
これがコードです。_A はヒープを格納する配列であり、Java 配列のインデックスは 0 から始まるため、インデックスは -1 です。
Max-Heapify を実行するには、ヘルパー関数交換を作成します。
それでは、ランダムな完全なバイナリ ツリーから Max ヒープを構築するにはどうすればよいでしょうか?次のようなヒープがあるとします。
ヒープの中央 (5 番目のノード) から開始して、ルートに 1 つずつ戻って max-heapify 操作を実行できます。それが完了すると、最大ヒープが得られます。これはそのデモビデオです:
次のようなコード:
注意深く見てみると、max-heap が順序付けられたデータ構造ではないことがわかります。すべての親ノードはその子ノードよりも大きくなりますが、左のサブノードは右のサブノードよりも大きくなる可能性もあり、小さくなる場合もあります。何らかの方法でバイナリ ツリーをトラバースするだけでは、順序付けされた配列を簡単に取得することはできません。では、ヒープを使用して数値を並べ替えるにはどうすればよいでしょうか?
私たちはルートが常に最大のものであることを知っています。したがって、ルートを最後のノードと交換し、ヒープから最後のノードを削除して、ルートを max-heapify することができます。その後、残りのヒープが有効な最大ヒープになり、これを何度でも行うことができます。常に最大の数値を後ろに置くので、順序付けられた配列が得られます。
この最大ヒープからソートを開始できます。
そしてこれが私たちのデモビデオです:
次のようなコード:
そして、max-heap は操作をサポートできますエキストラマックス、ルートを返して削除し、ヒープを縮小します。これを使用すると、最初に並べ替えることなく、最大数または k 番目の最大数を取得できます。次のようなコード:
したがって、max-heap を使用して数値を並べ替えることができます。あるいは、これを使用して最大数を取得したり、k 個の最大数を取得したりして、並べ替えるよりもコストを抑えることもできます。
GitHub アドレスhttps://github.com/tinyfool/leetcode/blob/master/src/CLRS/HeapSort.java
ヒープとヒープソートに関連する LeetCode の問題:
