阅读原文
堆排是基于堆的一种排序算法,对于堆的了解,请看什么是堆排序(如果对堆的插入和删除不清楚,强烈建议先看堆),今天我们聊聊堆排的思想,复杂度以及稳定性。
堆排思想
前情回顾:克给谦子解决了时间管理上的问题:什么是堆排序
过了几天后,谦子高兴地跑到老师跟前
1.png早知不来了,谦子心想
2.png谦子心想:上次去溪边游玩不是已经出过这个题吗,当时学会了冒泡排序,这次肯定不是那么简单,肯定和前几天的堆有关系
3.png删除中交换操作会破坏堆有序
但下沉操作会重新调整堆
谦子画了一个图解释道
4.png5.png
6.png删除包括三个步骤:
① 交换堆顶与堆最后一个元素
② 堆大小(heapSize)减一
③ 调整堆(sink(arr,1))
具体讲解请看:二叉堆
建堆
7.png8.png 9.png 10.png 11.png 12.png 13.png 14.png上浮(swim)操作会保持堆有序
注意:在下沉(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.png29.png 30.png 31.png 32.png所以问题变为:
① 高度最高多高(高度上界)
② 高度h有多少节点
这里你记住两个结论
谦子长舒一口气
n-1次删除 复杂度
33.png34.pngn-1次调用deleteMin
deleteMin中包含 swap操作和 sink操作
swap操作代价为常数,sink操作代价为lgn,swap操作相对于sink操作可以忽略不计
则相当于进行了n-1次sink操作
则一共花费的代价为:(n-1)*lgn ~ nlgn
故时间复杂度为O(nlgn)
稳定性
35.png谦子说着说着画了一个图
36.png 37.png摘录自:趣谈编程
网友评论