堆排序
2021-04-08 21:38:31 0 举报堆排序
作者其他创作
大纲/内容
交换
原理：每次将最大值移动到根节点，和尾交换，之后尾部排序完成，尾部脱离这棵树。
6
大值上移
2
5
0
创建最大堆
4
97
49
1
76
堆是一个完全二叉树（叶子节点只能出现在最下层和次下层）堆中每一个节点的值必须大于或者等于（小于或者等于)其左右子树所有节点的值
81
循环进行，每一次循环排好一个 数
13
此时max下标指向49所在下标
7
heapify
max = 父节点下标左子节点大于max，max = 左子节点下标右子节点大于max，max = 右子节点下标
35
堆排序是一种选择排序，，它的最好、最坏、平均时间复杂度为O(nlogn)与直接选择排序思想有点相同的就是每次都找最大值或者最小值
3
某节点为：i左节点：i*2 + 1右节点：i*2 + 2父节点：(i-1)/2
27
19
以红色线路去进行heapify创建最大堆从小到大：创建最大堆从大到小：创建最小堆
因为交换后不能确保49所在的子树是最大的，所以49所在的节点继续做heapify操作
可以用堆排序解决top-k的问题
0 条评论
下一页
