徹底的に山の並べ替えを解決します：二叉の山

二叉の山
二叉山とは何ですか
二叉山は本質的には完全な二叉樹で、二つのタイプに分けられています。

最大のヒープ：親ノードのいずれかの最大の山の値は、その左、右の子供ノードに等しい値（山の頂が全体の最大の要素です）

よりも大きいです。

最小ヒープ：最小ヒープのいずれかの親ノードの値は、その左、右の子供ノードに等しい値（山の頂が全体の最小要素）

よりも小さい。
二叉の山のルートノードを山頂といいます。
フォークスタックの基本操作

挿入ノード

ノード

を削除する。

により、二叉ヒープ

を構築する。
これらの操作はすべてヒープの自己調整に基づいています。いわゆる自己調整とは、山に合わない完全な二叉の木を一つの山に調整して、下は最小の山を例にしています。
挿入
ノード0を挿入するプロセス

削除
ノードを削除するプロセスと挿入するプロセスは、ちょうど逆であり、削除されたのは、スタックトップのノードである。例えば1を削除します

完全な二叉樹の構造を維持するために、山の最後の要素を一時的に山の頂部

に補充する。

元の10の位置

を削除します。

は、スタックトップのノード10に対してドロップ操作

を実行する。

ビルド
二叉ヒープを構築するということは、無秩序な完全二叉樹を二叉ヒープに調整し、本質はすべての非葉っぱノードを一度に沈下させることである。


二叉スタックコードの実現
第二の調査ヒープは完全な二叉樹であるが、その記憶方式はチェーン式ではなく、順序的に保存されており、言い換えれば、二叉ヒープのすべてのノードは配列に格納されている。

親ノードがparentの場合、左の子供は2*parent+1である。右の子供は2*parent+2です。

/**
 * @author ：zsy
 * @date ：Created 2021/5/17 9:41
 * @description：   
 */
public class HeapTest {
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        Heap heap = new Heap(arr);
        heap.upAdjust(arr);
        System.out.println(Arrays.toString(arr));
        arr = new int[]{7, 1, 3, 10, 5, 2, 8, 9, 6};
        heap = new Heap(arr);
        heap.buildHead();
        System.out.println(Arrays.toString(arr));
    }
}
class Heap {
    private int[] arr;
    public Heap(int[] arr) {
        this.arr = arr;
    }
    public void buildHead() {
        //            ，    
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            downAdjust(arr, i, arr.length);
        }
    }
    private void downAdjust(int[] arr, int parentIndex, int length) {
        int temp = arr[parentIndex];
        int childrenIndex = parentIndex * 2 + 1;
        while (childrenIndex < length) {
            //      ，          ，        
            if (childrenIndex + 1 < length && arr[childrenIndex + 1] < arr[childrenIndex]) {
                childrenIndex++;
            }
            //               ，    
            if (temp <= arr[childrenIndex]) break;
            //    ，    
            arr[parentIndex] = arr[childrenIndex];
            parentIndex = childrenIndex;
            childrenIndex = 2 * childrenIndex + 1;
        }
        arr[parentIndex] = temp;
    }
    public void upAdjust(int[] arr) {
        int childrenIndex = arr.length - 1;
        int parentIndex = (childrenIndex - 1) / 2;
        int temp = arr[childrenIndex];
        while (childrenIndex > 0 && temp < arr[parentIndex]) {
            //    
            arr[childrenIndex] = arr[parentIndex];
            childrenIndex = parentIndex;
            parentIndex = (parentIndex - 1) / 2;
        }
        arr[childrenIndex] = temp;
    }
}

結果:
[0,1,2,6,3,7,8,9,10,5]
[1,5,2,6,7,3,8,9,10]
締め括りをつける
この文章はここまでです。あなたに助けを与えたいです。私たちのもっと多い内容に注目してください。