堆排序详解

1. 什么是堆？

堆其实就是一颗完全二叉树
堆有大根堆和小根堆，望文生义，即是根节点分别是最大和最小节点。

2.堆的建立

堆的逻辑结构是完全二叉树，但是实际可以由数组来实现，通过下标变换来定位父节点和左右子节点。

完全二叉树中，下标为i 的节点
其父节点是 (i-1)/2
其左孩子是 i2+1
其右孩子是 i2+2

一个数组必定能够构建一颗完全二叉树，只需要按照层序从左往右放置节点即可。如下图所示：

由数组构造完全二叉树

但是这种方式建立的完全二叉树并非一定是堆。因为根节点还一定就是最小最大节点。

这里以大根堆为例，讲解堆的建立过程。

/**
     *  建堆
     * @param arr
     */
    public void InitHeap(int[] arr){
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) { // 逐个加入,每一个加入都维护成堆
            heapInsert(arr, i);
        }
    }
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {   // 比父节点大
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;     // 节点往上浮
        }
    }

   //  通过异或交换两值
    public void swap(int[] arr, int i, int j) {
        if (arr[i] != arr[j]) {
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
        }
    }

3.根弹出后堆的维护 heapify 过程

public static void heapify(int[] arr, int index, int size) {
        int left = index * 2 + 1;  
        while (left < size) {  
            // 左右节点需在未排序范围内
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;  // 选择左右节点中大者
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);   // 交换父节点与左右子节点中大者
            index = largest;    // 节点往下沉
            left = index * 2 + 1;  
        }
    }

4. 整个堆排序过程

  public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int size = arr.length;
        swap(arr, 0, --size);
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }