堆排序

堆排序

mmexport1520334289708.gif

阅读原文

堆排是基于堆的一种排序算法，对于堆的了解，请看什么是堆排序（如果对堆的插入和删除不清楚，强烈建议先看堆），今天我们聊聊堆排的思想，复杂度以及稳定性。

堆排思想

前情回顾：克给谦子解决了时间管理上的问题：什么是堆排序

过了几天后，谦子高兴地跑到老师跟前

1.png

早知不来了，谦子心想

2.png

谦子心想：上次去溪边游玩不是已经出过这个题吗，当时学会了冒泡排序，这次肯定不是那么简单，肯定和前几天的堆有关系

3.png

删除中交换操作会破坏堆有序
但下沉操作会重新调整堆

谦子画了一个图解释道

4.png

5.png

删除包括三个步骤：
① 交换堆顶与堆最后一个元素
② 堆大小(heapSize)减一
③ 调整堆(sink(arr,1))
具体讲解请看:二叉堆

6.png

建堆

7.png

上浮(swim)操作会保持堆有序

8.png

9.png

10.png

11.png

12.png

13.png

14.png

注意：在下沉(sink)某个节点的时候，这个节点的两个孩子必须是堆

堆排代码

15.png

克突然话锋一转

16.png

又要写代码，谦子心想，虽说心中这样想，但还是要写的，思考了一会，只见谦子写下了如下代码

/**
* 将传进来的无序数组变成小根堆
* @param arr a[1...n]为有效元素，a[0]为无效元素
*/
public void buildHeap(int[] arr) {
    // 从第一个非叶子节点开始sink调整，也就是堆大小的一半处
    for(int i = heapSize/2; i >= 1; i --) {
        sink(arr, i); // 调整以节点i为父节点的树为堆（符合堆有序）
    }
}

17.png

谦子解释道

18.png

过了一会谦子又写出了删除最小值的代码

/**
* 删除堆中最小的元素（通过heapSize--逻辑上删除）
* @param arr a[1...n]为有效元素，a[0]为无效元素
*/
private void deleteMin(int[] arr) {
    // 交换堆顶和堆最后一个元素
    swap(arr, index1, heapSize); 
    heapSize --;
    sink(arr, parentIndex:1); // 调整使之重新变成堆有序

}

19.png

前两个都写出来了，剩下的排序就很简单了，按照之前的思路，先建立一个小根堆，然后不断地删除堆顶最小元素，删除N-1次就OK了

/**
* 对给定数组arr排序，使之为降序
* @param arr a[1...n]为有效元素，a[0]为无效元素
*/
public void heapSize(int[] arr) {
    int N = arr.length-1;
    buildHeap(arr);    // 建小根堆
    // n个元素的小根堆，排序（删除堆顶）n-1次，数组就变成降序了
    for(int i = 1; i <= n-1; i ++) {
        deleteMin(arr);   // 删除arr数组中最小的值
    }
}

20.png

谦子解释道

21.png

谦子暗自惊叹老师的功力，不知不觉又学到了一个排序方法

时间复杂度

22.png

看到数学头疼的可以直接跳过看结论

谦子还没缓过神，又来了一个最让他头疼的时间复杂度

23.png

克拿出了笔和纸

24.png

建堆时间复杂度

25.png

叶子节点高度为0，下沉代价为0

谦子目不转睛地

26.png

所以问题变为：
① 高度最高多高（高度上界）
② 高度h有多少节点
这里你记住两个结论

29.png

30.png

31.png

32.png

谦子长舒一口气

n-1次删除复杂度

33.png

n-1次调用deleteMin
deleteMin中包含 swap操作和 sink操作
swap操作代价为常数，sink操作代价为lgn,swap操作相对于sink操作可以忽略不计
则相当于进行了n-1次sink操作
则一共花费的代价为：(n-1)*lgn ~ nlgn
故时间复杂度为O(nlgn)