ヒープソートアルゴリズムの解説とJava版実装

ヒープはデータ構造の中で重要な構造です。「ヒープ」の概念と操作を理解すれば、ヒープソートをすぐにマスターできます。

ヒープの概念
ヒープは、特別な完全なバイナリ ツリーです。完全なバイナリ ツリー内のすべてのノードの値がその子ノードよりも小さくない場合、それはラージ ルート ヒープ (またはラージ トップ ヒープ) と呼ばれます。小さなルート ヒープ (または小さなトップ ヒープ)。
配列 (ルート ノードは添字 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 サイトに注目してください。