堆排序

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

堆排思想

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

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

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

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

1
2
3
4
5
6
7
8
9
10
/**
* 将传进来的无序数组变成小根堆
* @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

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

1
2
3
4
5
6
7
8
9
/**
* 删除堆中最小的元素(通过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了

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 对给定数组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)

34.png

稳定性

35.png

谦子说着说着画了一个图

36.png

37.png

摘录自:趣谈编程

有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%