关于堆

在学习堆排序直线先来看看堆这个数据结构

堆的一个经典的实现是完全二叉树(complete binary tree)，这样实现的堆称为二叉堆(binary heap)。

满二叉树：除了叶子节点，所有的节点的左右孩子都不为空，就是一棵满二叉树，如下图：

可以看出：满二叉树所有的节点都拥有左孩子，又拥有右孩子。

完全二叉树：不一定是一个满二叉树，但它不满的那部分一定在右下侧，如下图：

关于堆详细的描述及实现方式这里不再赘述，网上资源很多，这里重点说一下堆的特性。
堆的特性：

• 必须是完全二叉树
• 任一结点的值是其子树所有结点的最大值或最小值

最大值时，称为“最大堆”，也称大顶堆；

最小值时，称为“最小堆”，也称小顶堆。

还有一点很重要，那就是如果把一个二叉堆按层次遍历打印出来放在一个数组中，那么对于任意一个有子节点的节点在数组中的索引index会满足下面的关系：

• leftChild = 2 * index + 1
• rightChild = 2 * index + 2

比如下面的二叉堆：

关于堆排序

堆排序顾名思义，是利用堆这种数据结构来进行排序的算法。

堆是一种优先队列，有两种实现，最大堆和最小堆，由于这里排序按升序排，所以暂且最大堆。

可以把堆看成一棵完全二叉树，位于堆顶的元素总是整棵树的最大值，每个子节点的值都比父节点小，由于堆要时刻保持这样的规则特性，所以一旦堆里面的数据发生变化，必须对堆重新进行一次构建。

既然堆顶元素永远都是整棵树中的最大值，那么我们将数据构建成堆后，只需要从堆顶取元素即可。每次取完根节点，将二叉树的末尾节点移到根节点位置（这里的末尾节点指的是，二叉树按照层序遍历之后的最后一个节点，如上面图中的节点5）。

讲到这里你可能说需要建立一棵真正的二叉树，当然可以，只是没必要，堆排序的精髓并不是真的要用节点类实现一个二叉堆，而是利用堆的思想，通过将数组内部元素进行调整的方式来实现一个虚拟的堆，但是最终达到的效果跟真正通过建立一棵二叉堆来实现排序是一样的。

堆排序其实总的来说就三步：

1. 待排序数组
2. 建立二叉堆
3. 取二叉堆顶元素

这三步都可以通过调整数组中的元素位置来实现！

1. 待排序数组就是给定的待排序数组

2. 建立二叉堆的过程有点麻烦，也是堆排序的精髓，其实看代码更好理解一些。

   当我们拿到一个待排序数组后，我们可以把通过一定的规则访问数组元素的方式建立一棵虚拟的二叉树，就是前面所说的leftChild = 2 * index + 1及rightChild = 2 * index + 2，有了这个规则，我们可以得到任意一个元素的左右子节点。

   但是现在的二叉树只满足了它是一个完全二叉树的特性，任一结点的值是其子树所有结点的最大值的`特性还需要一定的操作。

   那就是下沉操作，当一个节点小于其中一个子节点时，就将此节点与那个较大的子节点对调。如果这个操作是自顶向下的，那么就比较麻烦，所以这里的实现是自底向上。

3. 取二叉堆顶元素，就代表将数组中的第一个元素与末尾元素对调。

下面直接上代码，不得不说堆排序的代码真的很巧妙：

public class Solution {

    public static void heapSort(int[] arr) {
        int length = arr.length;
        buildHeap(arr, length);

        for ( int i = length - 1; i > 0; i-- ) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            length--;
            sink(arr,0,length);
        }
    }

    private static void buildHeap(int[] arr, int length) {
        for (int i = length / 2; i >= 0; i--) {
            sink(arr,i,length);
        }
    }

    private static void sink(int[] arr, int index, int length) {
        int leftChild = 2 * index + 1; 
        int rightChild = 2 * index + 2; 
        int present = index; 

        if (leftChild < length && arr[leftChild] > arr[present]) {
            present = leftChild;
        }
        if (rightChild < length && arr[rightChild] > arr[present]) {
            present = rightChild;
        }
        if (present != index) {
            int temp = arr[index];
            arr[index] = arr[present];
            arr[present] = temp;

            sink(arr,present,length);
        }
    }
}

解说代码：

package sort.heap;

/**
 * @Author Hory
 * @Date 2020/10/2
 */
public class Solution {

    public static void heapSort(int[] arr) {
        int length = arr.length;
        //构建堆
        buildHeap(arr, length);

        for ( int i = length - 1; i > 0; i-- ) {
            //将堆顶元素与末尾元素调换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //数组长度-1 隐藏堆尾元素
            length--;
            //将堆顶元素下沉 目的是将最大的元素浮到堆顶来
            sink(arr,0,length);
        }
    }

  
  	//构建堆的过程就是一个个节点下沉的过程，只不过这个过程是自底向上
  	//为什么是自底向上？
  	//那就要知道sink这个函数的功能：对指定的元素为根节点以下的节点进行下沉，直到遇到一个节点大于其左右子节点才会退出。但是就算退出了，也不能保证当前节点的子节点的子节点是否满足堆的特性，所以，如果我们自底向上的话，每次执行当前节点，那么它下面的节点全是执行过下沉操作的，这就保证了以当前的节点为根节点的整个树都是满足堆特性的
  	//为什么是i = length/2 ？
  	//因为是自底向上，所以arr[length/2]这个节点刚好最后一个节点的父节点
    private static void buildHeap(int[] arr, int length) {
        for (int i = length / 2; i >= 0; i--) {
            sink(arr,i,length);
        }
    }

    /**
     * 下沉调整
     * 该sink函数的功能就是对指定的元素为根节点以下的节点进行下沉，直到遇到一个节点大于其左右子节点才会退出
     * @param arr 数组
     * @param index 调整位置
     * @param length 数组范围
     */
    private static void sink(int[] arr, int index, int length) {
        int leftChild = 2 * index + 1; //左子节点下标
        int rightChild = 2 * index + 2; //右子节点下标
        int present = index; //要调整的节点下标

      	//这里也不用判断左右子节点是否为空，因为如果为空，那么:
      	// leftChild = 2 * index + 1; 这个结果肯定是大于等于length的
        //下沉左边
        if (leftChild < length && arr[leftChild] > arr[present]) {
            present = leftChild;
        }

        //下沉右边
        if (rightChild < length && arr[rightChild] > arr[present]) {
            present = rightChild;
        }

      	//经过两个if判断下来，最终present指向的值肯定是父节点、左右子节点中最大的那个
      	//不相等证明present肯定指向了其中一个子节点
        if (present != index) {
            //交换值
            int temp = arr[index];
            arr[index] = arr[present];
            arr[present] = temp;

            //继续下沉
            sink(arr,present,length);
        }
      	//最后发现sink这个递归函数貌似没有通常的那种递归出口，其实就包含在最后一个if语句中
      	//只要最后一个if语句满足，就会不断执行sink这个函数，直到最终判断一个节点大于其左右子节点，最终才不会进入if中执行sink
    }
}