Rai*_*noa 0 sorting algorithm heapsort max-heap
我正在使用算法,特别是heapsort.根据我的理解,heapsort算法涉及通过首先将其转换为最大堆来准备列表.
转过身来
[2,8,5,3,9,1]
进入
[9,8,5,3,2,1]
使用heapsort我应该用1交换9.但是通过在最大堆积之后直接查看数组,我看到按降序排列的排序列表.当列表已按递减顺序排序时,为什么需要交换？
这只是我观看后的想法:https: //www.youtube.com/watch？v = 2DmK_H7IdTo
将它作为堆后,它不一定按降序排序.
堆只需要每个节点都比它的子节点更大(或更小,对于最小堆),但是没有说明子节点的顺序,也没有说明不同级别节点的关系(其中一个节点不是直接的后代)另一个,看到5和6下面).这意味着这也是一个有效的堆:
9
/ \
5 8
/ \ /
1 2 6
[9, 5, 8, 1, 2, 6]