Javaスタックの順序付けアルゴリズムの詳細解

ヒープはデータ構造の中の重要な構造であり、「ヒープ」の概念と操作を理解することで、私たちが迅速に積み上げ順序を把握するのを助けることができます。
ヒープの概念
ヒープは特殊な完全二叉樹です。本の完全な二叉樹のすべてのノードの値がそのサブノードより小さい場合は、大きなルートヒープ（または大きなトップヒープ）と呼ぶ。すべてのノードの値は、そのサブノードより大きくなく、小さなルートヒープ（または小さなトップヒープ）と呼ばれる。
配列（0番下付きのルートノード）では、次の式が容易に得られます。
1.iとラベル付けされたノードの親ノード座標は(i-1)/2である。
2.iとラベル付けされたノードで、左サブノードの座標は2＊i＋1、右サブノードは2＊i＋2です。
ヒープの建立とメンテナンス
ヒープはいろいろな操作に対応できますが、今私達が関心を持っているのは二つの問題だけです。
1.無秩序配列を指定しましたが、どうやって積み上げられますか？
2.スタッドトップ要素を削除した後、どのように配列を調整して新しい山になりますか？
まず第二の問題を見ます。私たちは既に既成の大きな根っこがあると仮定します。今はルートを削除しましたが、他の要素は移動していません。何が起こったか考えてみます。根が空いていますが、他の元素はまだ山の性質を維持しています。最後の要素（コードA）をルート要素の位置に移動できます。特殊な場合でなければ、山の性質は破壊されます。しかし、これはAがそのサブ要素より小さいだけです。そこで、Aとこのサブ元素を位置を変えることができます。Aがそのすべてのサブ要素より大きい場合、ヒープは調整されました。そうでなければ、上述のプロセスを繰り返すと、A元素は樹形構造において常に「沈下」し、適切な位置に至るまで、配列が再びスタックの性質を回復する。上記の過程は一般に「スクリーニング」と呼ばれ、方向は明らかに上から下までです。
要素を削除するのも同じです。新しい要素を挿入するのも同じです。違っているのは、新しい元素を最後に置いて、その親ノードと比較します。つまり下から上へフィルタします。
最初の問題はどう解決しますか？
私が見たデータ構造の本の多くは、最初の非葉っぱの結点から下に向けて選別しています。この方法は「スクリーニング法」と呼ばれていますが、n/2の要素をフィルタリングする必要があります。
しかし、私たちはまた「無から有」の考え方を参考にすることができます。私たちは最初の元素を一つの山と見なして、その中に新しい元素を絶えず追加します。この方法は「挿入法」と呼ばれ、要素を循環的に挿入する必要があります。
スクリーニング法と挿入法は違っていますので、同じデータでは、ヒープが一般的に違います。
大体において山を理解した後に、積み上げて並べばいいです。
アルゴリズムの概要/考え方
昇順のシーケンスが必要ですが、どうすればいいですか？最小の山を作って、毎回ルート要素を出力します。しかし、この方法は追加の空間を必要としています。そうでないと、大量の元素移動を引き起こし、その複雑さはO(n^2)まで上昇します。その場で並べ替える必要があるとしたら、（O（n）空間の複雑さがあってはいけません。）どうすればいいですか？
方法があります。最大ヒープを作って、最後の位置で最大値を出力し、最後の位置で出力回数が大きい値を出力します。出力の最大要素は一回目の空間が空いていますので、私達はちょうどこのような元素を置くことができます。余分な空間が必要ではありません。綺麗な考えですか？

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;
  }
}

以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。