堆排 | 晨星的博客

一个比较经典的的排序算法

堆排的由来

堆排序（英语：Heapsort）是指利用二叉堆这种数据结构所设计的一种排序算法。由罗伯特·弗洛伊德发明。
罗伯特·弗洛伊德：
计算机科学家，图灵奖得主，前后断言法的创始人，堆排序算法和Floyd-Warshall算法的创始人之一。[1]

基本原理

堆（特指大根堆）是一种特殊的二叉树，在堆的数据结构中，堆中的最大值总是位于根节点。
堆排就是用数组存储堆的结构（层序遍历）并进行排序

如果初始索引是0 那么可以看出一个节点的左孩子索引

$2*N+1$

右孩子索引 为 左孩子索引 +1

父节点索引

$[(index - 1) / 2]$

然后对数组进行如下过程定义：

heapinsert：向堆中插入数据，并保持堆的特性
heapify：移除堆顶元素（即最大值），再重新组织堆的特性

代码实现

heapinsert：向堆中插入数据，并保持堆的特性

因为前面的数组已经调整好了，当我们插入尾部后只要比父节点大就往上移，同时与父节点的交换并不会影响下面的子节点的堆特性（因为父节点相对于子节点本来就是最大的）
（是一个从下往上的过程）

代码如下：

public static void heapinsert(int[] arr, int index) {
	//只要大于原先父节点就往上跳
    while (arr[index] > arr[(index - 1) / 2]) {
        TestMachine.swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

heapify：移除堆顶元素（即最大值），再放入一个新值，再重新堆化

移除时只需要把堆的最后一个元素（即数组对应的索引）与堆顶的元素交换，对所用堆元素进行heapify过程，就可以实现数组的从小到大的排序（是一个从上往下的过程）

代码如下：

//index 当前索引（传入0） size 堆的规模
public static void heapify(int[] arr, int index, int size) {
    //左孩子的索引
    int left = 2 * index + 1;
    //没有越界就继续
    while (left < size) {
        //右孩子的索引
        int right = 2 * index + 2;
        //需要交换的位置
        int exchange = index;
        if (right < size) 
            //没有越界就继续
            exchange =
            	//右边是不是大于当前位置
                arr[right] > arr[index] ?      
                        ( //是 判断左边是否更大
                                arr[right] > arr[left] ? right : left 
                        )
                        :
                        ( //不是 判断左边是否比当前位置大
                                arr[left] > arr[index] ? left : index
                        );
        else if (arr[left] > arr[index]) 
            //右边越界判断左边是否是大于
            exchange = left;
        //如果exchange改变则交换
        if (exchange != index) {
            //数组对应的索引进行交换
            TestMachine.swap(arr, exchange, index);
            index = exchange;//当前指针记录进行下一次heapify
            left = 2 * index + 1; //计算左孩子的索引
        } else break;//没有改变 则堆的结构已经改变完成 退出
    }
}

整个排序的算法

代码如下：

public static void heapSort(int[] arr) {
    
    if (arr == null || arr.length == 0 || arr.length == 1) return;

    //O(N*logN) 可以优化
    //数组进行堆化
    for (int i = 0; i < arr.length; i++) {//O(N)
        heapinsert(arr, i);//O(logN)
    }
		
    //开始排序
    int len = arr.length - 1;
    TestMachine.swap(arr, 0, len);
    while (len > 0) {
        //第一个数（最大值 ）移除 对剩余数据进行heapify 重新进行堆化 
        // 重复过程直到全部排序完成
        heapify(arr, 0, len);
        TestMachine.swap(arr, 0, --len);
    }

}

优化

对上面的数组堆话过程可以继续进行优化

由于每次heapinsert都是一个logN的过程（即树的高度） 也就是时间复杂度O(N*logN)

而如果我们从下往上来进行数组堆化

也就是修改成

//O(N)
//数组进行堆化
for (int i = arr.length - 1; i >= 0; i--) {
    heapify(arr, i, arr.length);
}

这些代码每一层（堆中）复杂度都是递增的
但上面的代码是从上往下也就是底下数据量越多而且越复杂
而优化后是从下往上也就是越往上越复杂但数据量也越少

复杂度O(N)的证明：

由于二叉树的特性每层节点的heapify过程最多走层高而每层节点的个数也可以通过二叉树的性质求出

所以从底层加到顶层的次数：

$S_n=\frac {N}{2}*1 + \frac {N}{2^2}*2 + \frac {N}{2^3}*3 + \frac {N}{2^4}*4 + ......$

令

$2S_n=\frac {N}{2}*2 + \frac {N}{2^1}*2 + \frac {N}{2^2}*3 + \frac {N}{2^3}*4 + ......$

$2S_n-S_n=N+\frac {N}{2^1}*1 + \frac {N}{2^2}*1 + \frac {N}{2^3}*1 + ......$

后面就是一个等比数列求和（且q=1/2）由于时间复杂度只取高次位得复杂度O(N)

总结

时间复杂度的函数为

$O(N*log(N))$

空间复杂度有限几个变量

$O(1)$

由于堆的特性数据是无法保存顺序的所以是一个不稳定的排序算法

每日一句

如果印钞票能消除贫困的话，那么印文凭也就可以消除愚蠢了。——阿根廷总统哈维尔·米莱

参考

百度百科