[数据结构与算法]Algorithm-左程云-堆排序

?本文是学习了左神教学视频后编码完成的，相对于上一篇堆排序算法Algorithm-排序算法-堆排序_lreis2010-CSDN博客过程更加清晰简练，可以先通过上一篇文章了解原理，再来学习这个算法的具体实现。

1.构建最大堆

在堆中插入一个新的元素，需要判断该元素与父节点之间的大小关系进行适当的调整，保证当前数据结构是一个最大堆。

构建最大堆的过程是一个自下而上的调整过程。

    // 插入新的数，调整堆为最大堆
    // 自下而上的调整
    private void heapInsert(int[]arr, int index){
        int parent = (index - 1) / 2;
        while (arr[index] > arr[parent]){
            // 子节点的值大于父节点
            swap(arr, index, parent);
            index = parent;
            parent = (index - 1) /2;
        }
    }

2.删除一个节点

删除一个节点的过程是将队尾元素与要删除的节点进行交换，同时减少堆的大小，遮盖被交换出去数据的存在。

原来的队尾元素插入到新的位置后，需要进行一次自上而下的调整，重新构建最大堆。

    // 某个数在index位置，向下移动保持最大堆
    // 自上而下的调整
    private void heapfy(int[]arr, int index, int heapSize){
        int left = index * 2 + 1;
        // 如有有子孩子就判断
        while (left < heapSize){
            // 左右子节点之间比较最大值
            int largest = (left + 1 < heapSize && arr[left] < arr [left +1])?  left + 1 : left;
            // 父子之间比较最大值
            largest = arr[largest] > arr[index] ? largest : index;
            // 父节点已经是最大值
            if (largest == index){
                break;
            }
            swap(arr, index, largest);
            index = largest;
            left = index * 2 + 1;
        }
    }

3.堆排序

?堆排序是基于以上两个过程的，整体过程包括

• 构建最大堆
• 将最大堆的队头元素和队尾元素交换位置，完成最大值的排序，并重新调整数组为最大堆
• 重复第二步，直到排序完成。

    // 堆排序
    private void heapSort(int[]arr){
        if (arr == null || arr.length < 2){
            return;
        }
        // 构建最大堆
        int heapSize = arr.length;
        for (int i = 0; i< heapSize; i++){
            heapInsert(arr, i);
        }
        while (heapSize > 0){
            // 将最大值移动到队列尾部并遮蔽最大值
            swap(arr, 0, --heapSize);
            // 队尾写入对头，自上而下调整为最大堆
            heapfy(arr, 0, heapSize);
        }
    }