【算法学习】堆排序建立最大堆

本文代码均转自：

作者：早就戒了
来源：CSDN
原文：https://blog.csdn.net/qq_37169817/article/details/79777264
版权声明：本文为博主原创文章，转载请附上博文链接！

public class HeapSort { 
    public static int[] maxHeap(int[] array) { 
        // 1.构建大顶堆 
        for (int i = array.length / 2 - 1; i >= 0; i--) { 
            // 从第一个非叶子结点从下至上，对于数组从右至左调整结构 
            adjustHeap(array, i, array.length); 
            } 
        return array; 
        } 
    
    private static void adjustHeap(int[] array, int i, int length) { 
        int parent = array[i]; 
        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) { 
            // 2*i+1表示左节点，k = k * 2 + 1表示继续调整子节点 
            if (k + 1 < length && array[k] < array[k + 1]) 
                k = k + 1;// 找到子节点中更大的节点 
            if (array[k] > parent) { 
                    array[i] = array[k];// 父节点变为更大的值 
                    i = k;// 修改i的值，使之成爲新的要調整的父節點 
                } else { 
                    break;// 表示无需调整，因为是自底向上的 
                    } 
            } 
        array[i] = parent;// 将temp值放到最终的位置 
        }
    
    public static void main(String[] args) { 
        int[] array = { 4, 6, 8, 5, 9 }; 
        int[] maxHeap = maxHeap(array); 
        for (int i : maxHeap) { 
            System.out.print(i + " "); 
            } 
        } 
    }

建大根堆堆思路整理：

1.找到堆中第一个非叶子结点（N0），从它开始调整左右子树。

*第一个非叶子结点的下标为：length/2 -1

*左右子树调整过程：找到其中的较大值结点Ngreater，然后与N0值作比较，如果N0<Ngreater则将两者交换，并继续调整Ngreater的叶子结点（虽然是自底向上调整的，

但是可能在某些parent下降的过程中破坏了底下子树的大小排列规则。）如果N0>=Ngreater直接开始（退出了adjustHeap函数）调整下一个非叶子结点。

2.通过循环调用adjustHeap将所有的非叶子几点调整完成。

堆排序思路：

1.建立初始堆后，将堆顶元素（最大值）与堆中最后一个元素交换，然后调整数组（堆）中的前n-1个元素。（即把数组末尾作为有序区）

2.调整到堆中只剩一个元素时，排序完成。

堆排序代码：

public static void sort(int []arr){ 
    //1.构建大顶堆
    for(int i=arr.length/2-1;i>=0;i--){ 
        adjustHeap(arr,i,arr.length); 
        } 
    //2.调整堆结构+交换堆顶元素与末尾元素 
    for(int j=arr.length-1;j>0;j--){ 
        swap(arr,0,j);//将堆顶元素与末尾元素进行交换 
        adjustHeap(arr,0,j);//重新对堆进行调整
        } 
    }