堆排序 Heap Sort

堆排序是指利用堆这种数据结构所设计的一种 排序 算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆的特征

• 堆的数据结构近似完全二叉树，即每个节点存在两个子节点
• 当节点的值小于或等于父节点值，大于或等于子节点值称为大顶堆（也即根节点的值最大）
• 当节点的值大于或等于父节点值，小于或等于子节点值称为小顶堆（也即根节点的值最小）
• 若当前节点的索引为 k , 那么左子节点索引为 2 k + 1, 右子节点索引为 2 k + 2, 父节点索引为 (k - 1) / 2

在本文中我们以大顶堆为例

堆的动作 - 上浮

上浮 ： 是指在构建堆时，若节点的值大于父节点则将当前节点与父节点互相交换；直至该节点小于父节点时终止上浮（可以理解为一个新入职的员工能力出众晋升更高的职位）； 效果如下图

代码如下：

private void siftUp(int k) {
		// k == 0 时表明上浮到根节点，结束上浮操作
        while (k > 0) {
        	// 获取父节点索引
            int parent = (k - 1) / 2;

            // 小于父节点时退出，结束上浮操作
            if (less(parent, k)) {
                break;
            }
            // 与父节点交换数据
            swap(parent, k);
            // 改变 k 的指向 继续上浮
            k = parent;
        }
    }
复制代码

堆的动作 - 下沉

下沉 ： 是指构建堆的过程中，若当前节点值小于子节点则将当前节点与子节点互相交换，直至该节点大于子节点时终止下沉（可以理解为一个leader能力平庸的时候被降职的过程，是不是有点很惨）； 效果如下图

代码如下：

private void siftDown (int k, int length) {
        // 获取左子节点索引
        int childIndex = 2 * k + 1;
		// 判断是否存在子节点
        while (childIndex < length) {
            // 判断左右子节点 查找最大的子节点 
            if (childIndex + 1 < length && !less(childIndex, childIndex + 1)) {
                childIndex++;
            }

            // 若当前节点大于子节点 退出循环
            if (less(k, childIndex)) {
                break;
            }

            // 判断当前节点是否小于子节点, 若小于执行交换
            swap(k, childIndex);
            // 改变 k 指向
            k = childIndex;

            childIndex = 2 * k + 1;
        }
    }
复制代码

堆排序

那么如何采用堆的数据结构，对一个无序的数组进行排序呢 ？

• 首先将无序数组构造成一个最大堆，此时根节点为最大值
• 将最后一个节点与根节点值交换，剔除最大值节点；
• 将剩下节点重新执行构造堆
• 循环执行第 2,3 两步操作

无序数组构造堆

将无序数组构造堆，可以采用上浮， 也可以采用下沉的方式处理

如上图所示，为采用 上浮 的方式构建堆，其流程是依次从下标为 0 开始对数组的每个元素进行上浮操作，直至最后得到一个有序的大顶堆。

如上图所示，为采用 下沉 的方式构建堆，其流程是依次从非叶子节点 开始对数组的每个元素进行下沉操作，直至最后得到一个有序的大顶堆。

代码如下：

for (int i = 0; i < array.length; i++) {
		// 上浮方式构建堆
        siftUp(i);
    }
复制代码

// 因为堆是完全二叉树的特性, 所以下标小于等于 array.length / 2 的节点为非叶子节点
// 采用下沉的方式 从下往上构建子堆
    for (int i = array.length / 2; i >= 0; i--) {
        siftDown(i, array.length);
    }
复制代码

完成初始堆构造之后，剩下的工作就是重复进行以下逻辑(这个地方就不画图了)：

• 尾节点和根节点交换元素
• 剔除尾节点，对余下的元素进行子堆构造(构造堆的方式与初始堆一样)

完整代码如下 ：

public class HeapSort {

    private int[] array;

    public HeapSort(int[] array) {
        this.array = array;
    }

    private boolean less (int i, int j) {
        return array[i] > array[j];
    }

    private void swap (int k, int j) {
        int temp = array[k];

        array[k] = array[j];
        array[j] = temp;
    }

    /**
     * 下沉操作
     *
     * @param k
     */
    private void siftDown(int k, int length) {
        // loop
        // 判断是否存在子节点
        int childIndex = 2 * k + 1;

        while (childIndex < length) {
            // 查找最大的子节点
            if (childIndex + 1 < length && !less(childIndex, childIndex + 1)) {
                childIndex++;
            }

            // 若当前节点大于子节点 退出循环
            if (less(k, childIndex)) {
                break;
            }

            // 判断当前节点是否小于子节点, 若小于执行交换
            swap(k, childIndex);
            // 改变 k 指向
            k = childIndex;

            childIndex = 2 * k + 1;
        }
    }

    /**
     * 上浮操作
     *
     * @param k
     */
    private void siftUp(int k) {
        while (k > 0) {
            int parent = (k - 1) / 2;

            // 小于父节点时退出
            if (less(parent, k)) {
                break;
            }
            // 与父节点交换数据
            swap(parent, k);
            // 改变 k 的指向
            k = parent;
        }
    }

    public void sort () {
        // 构造堆
        for (int i = 0; i < array.length; i++) {
            siftUp(i);
        }

        print();

        int n = array.length - 1;

        while (n > 0) {
            // 因为每次完成堆的构造后, 根节点为最大(小)值节点
            // 将根节点与最后一个节点交换
            swap(0, n);

            for (int i = 0; i <= n - 1; i++) {
                // 排除有序的节点
                // 重新构造堆
                siftUp(i);
            }

            print();

            n--;
        }
    }

    private void sort1 () {
        // 构建堆
        // 因为堆是完全二叉树的特性, 所以下标小于等于 array.length / 2 的节点为非叶子节点
        // 采用下沉的方式 从下往上构建子堆
        for (int i = array.length / 2; i >= 0; i--) {
            siftDown(i, array.length);
        }

        print();

        int n = array.length - 1;

        while (n > 0) {
            // 因为每次完成堆的构造后, 根节点为最大(小)值节点
            // 将根节点与最后一个节点交换
            swap(0, n);

            for (int i = n / 2; i >= 0; i--) {
                // 排除有序的节点
                // 重新构造堆
                siftDown(i, n);
            }

            print();

            n--;
        }

    }
    private void print () {
        for (Integer num : array) {
            System.out.print(num);
            System.out.print(",");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        int[] array = {10, 40, 38, 20, 9, 15, 25, 30, 32};

        new HeapSort(array).sort();

        System.out.println("");

        new HeapSort(array).sort1();
    }
}

复制代码

小结 ： 堆排序在哪里应用到了呢 ？ 可参考优先队列 PriorityQueue 的实现