ヒープはデータ構造の中で重要な構造です。「ヒープ」の概念と操作を理解すれば、ヒープソートをすぐにマスターできます。
ヒープの概念
ヒープは、特別な完全なバイナリ ツリーです。完全なバイナリ ツリー内のすべてのノードの値がその子ノードよりも小さくない場合、それはラージ ルート ヒープ (またはラージ トップ ヒープ) と呼ばれます。小さなルート ヒープ (または小さなトップ ヒープ)。
配列 (ルート ノードは添字 0 に格納されます) では、次の式を簡単に取得できます (これら 2 つの式は非常に重要です):
1. 添字 i を持つノード、親ノードの座標は (i-1) ) /2;
2. 添字が i のノードの場合、左側の子ノードの座標は 2*i+1 であり、右側の子ノードは 2*i+2 です。
ヒープの作成とメンテナンス
ヒープはさまざまな操作をサポートできますが、ここで考慮するのは 2 つの質問だけです:
1. 順序付けされていない配列をヒープとして構築するにはどうすればよいですか?
2. ヒープの先頭要素を削除した後、配列を新しいヒープに調整するにはどうすればよいですか?
まず 2 番目の質問を見てみましょう。すでに大きな根の山が準備できていると仮定します。これでルート要素は削除されましたが、他の要素は移動していません。何が起こるかを考えてください。ルート要素は空ですが、他の要素は依然としてヒープの性質を維持しています。最後の要素 (コード名 A) をルート要素の位置に移動できます。特殊な場合ではない場合、ヒープの性質は破壊されます。しかし、これは単に A がその子の 1 つよりも小さいためです。したがって、A とこのサブ要素の位置を交換できます。 A がそのすべてのサブ要素よりも大きい場合はヒープが調整され、それ以外の場合は上記のプロセスが繰り返され、適切な位置に到達するまで A 要素がツリー構造内に「沈み込み」続け、配列がヒープを取り戻します。プロパティ。上記のプロセスは一般に「スクリーニング」と呼ばれますが、その方向性は明らかにトップダウンです。
要素を削除する場合も同様であり、新しい要素を挿入する場合も同様です。違いは、新しい要素を最後に配置してからその親ノードと比較すること、つまりボトムアップ フィルタリングであることです。
それでは、最初の問題をどうやって解決すればよいでしょうか?
私が読んだデータ構造の本の多くは、最初の非リーフノードからルート要素がフィルタリングされるまでフィルタダウンします。この方法は「スクリーニング方法」と呼ばれ、n/2 個の要素をスクリーニングするループが必要です。
しかし、私たちは「無から有を生み出す」というアイデアからも学ぶことができます。最初の要素をヒープとして扱い、そこに新しい要素を追加し続けることができます。この方法は「挿入方法」と呼ばれ、ループ内に (n-1) 個の要素を挿入する必要があります。
フィルタリング方法と挿入方法が異なるため、同じデータに対して作成されるヒープは通常異なります。
ヒープについて一般的に理解したら、ヒープのソートは当然のことです。
アルゴリズムの概要/アイデア
昇順シーケンスが必要ですが、どうすればよいでしょうか?最小ヒープを構築して、毎回ルート要素を出力できます。ただし、この方法には追加のスペースが必要です (そうしないと、多数の要素が移動され、複雑さが O(n^2) まで上昇します)。その場で並べ替える必要がある場合 (つまり、O(n) 空間の複雑さが許可されない場合) はどうすればよいでしょうか?
方法はあります。最大のヒープを構築し、それを逆方向に出力し、最後の位置で最大値を出力し、最後の位置で 2 番目に大きい値を出力します。毎回出力される最大の要素によって最初のスペースが解放されるため、このような要素には追加のスペースは必要ありません。なかなかいいアイデアですね。
public class HeapSort { public static void main(String[] args) { int[] arr = { 50, 10, 90, 30, 70, 40, 80, 60, 20 }; System.out.println("排序之前:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } // 堆排序 heapSort(arr); System.out.println(); System.out.println("排序之后:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } /** * 堆排序 */ private static void heapSort(int[] arr) { // 将待排序的序列构建成一个大顶堆 for (int i = arr.length / 2; i >= 0; i--){ heapAdjust(arr, i, arr.length); } // 逐步将每个最大值的根节点与末尾元素交换,并且再调整二叉树,使其成为大顶堆 for (int i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换 heapAdjust(arr, 0, i); // 交换之后,需要重新检查堆是否符合大顶堆,不符合则要调整 } } /** * 构建堆的过程 * @param arr 需要排序的数组 * @param i 需要构建堆的根节点的序号 * @param n 数组的长度 */ private static void heapAdjust(int[] arr, int i, int n) { int child; int father; for (father = arr[i]; leftChild(i) < n; i = child) { child = leftChild(i); // 如果左子树小于右子树,则需要比较右子树和父节点 if (child != n - 1 && arr[child] < arr[child + 1]) { child++; // 序号增1,指向右子树 } // 如果父节点小于孩子结点,则需要交换 if (father < arr[child]) { arr[i] = arr[child]; } else { break; // 大顶堆结构未被破坏,不需要调整 } } arr[i] = father; } // 获取到左孩子结点 private static int leftChild(int i) { return 2 * i + 1; } // 交换元素位置 private static void swap(int[] arr, int index1, int index2) { int tmp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = tmp; } }
ヒープ ソート アルゴリズムの詳細な説明と Java バージョンの実装に関連する記事については、PHP 中国語 Web サイトに注目してください。