【算法实践】他山之石,可以攻玉--利用完全二叉树快速实现堆排序

时间:2022-12-22 11:03:57

前言

什么是堆

堆是一种数据结构,它是完全二叉树或者是近似完全二叉树的一种数据结构,树中每个结点的值都不小于(或不大于)其左右孩子结点的值。

何为完全二叉树

完全二叉树是一种特殊的二叉树,完全二叉树是除了最后一层之外的其他每一场层都被完全填充,叶子节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树,也就是说所有节点都保持向左对齐。如果想了解更多关于二叉树的介绍,可参考之前写的一篇文章《​​【数据结构实践】手把手带你快速实现自定义二叉树​​》

对完全二叉树来说,较为简洁的实现方法就是使用数组来存储完全二叉树。这样结点就按层序存储于数组中,其中第一个结点将存储于数组中的1号位,并且数组i号位表示的结点的左孩子就是2i号位,而右孩子则是(2i+1)号位。

什么是堆排序

堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法,堆排序是将数据看成完全二叉树,然后根据完全二叉树的特性来进行排序的一种排序算法,这有点草船借箭的妙用。正所谓他山之,石可以攻玉。在堆排序中,堆具体可分为最大堆和最小堆,也有人称他们为大顶堆和小顶堆,如果父节点的值大于或等于孩子结点的值,那么称这样的堆为最大堆,这时每个节点的值都是以其为根结点的子树的最大值,即最大堆要求节点的元素都大于其对应的叶子节点,通常被用来进行升序排序,如果父节点的值小于或等于孩子结点的值,那么称这样的堆为最小堆,这时每个节点的值都是以其为根结点的子树的最小值,即最小堆要求节点的元素都小于其对应的叶子节点,通常被用于降序排序。堆一般用于优先队列的实现,而优先队列默认情况下使用的是最大堆。

小结:

最大堆:每个节点的值都大于或者等于它的左右子节点的值。

最小堆:每个节点的值都小于或者等于它的左右子节点的值。

如下图:

【算法实践】他山之石,可以攻玉--利用完全二叉树快速实现堆排序

【算法实践】他山之石,可以攻玉--利用完全二叉树快速实现堆排序

以最大堆为例,利用最大堆的结构特点,每个最大堆的根节点必然会是数组中最大的元素,构建一次最大堆,就可以获取数组中最大的元素。剔除最大元素后,反复构建剩下的数字为最大堆,获取根元素,最终保证数组有序。最大堆和最小堆是对称关系,学会其中一种即可

综上所述我们可以得出以下性质:

对于最大堆:arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

对于最小堆:arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

【算法实践】他山之石,可以攻玉--利用完全二叉树快速实现堆排序

堆排序的算法设计

具体步骤如下:

  1. 将待排序的数组构造成一个最大堆,根据最大堆的性质,当前堆的根节点(堆顶)就是序列中最大的元素
  2. 数组转换成最大堆之后,将堆顶元素取出,然后将剩下的节点重新构建为最大堆
  3. 重复步骤2,如此反复,直到剩余数只有一个时结束,从第一次构建大顶堆开始,每一次构建,我们都能获得一个序列的最大值
  4. 交换数据,最后,就得到一个有序的数组了

【算法实践】他山之石,可以攻玉--利用完全二叉树快速实现堆排序

代码实现

1.定义最大堆函数,传入当前节点的位置,左孩子位置是2*root+1.调整位置使堆顶元素最大

def siftdown(arr, node, end): #arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]
root = node # 当前节点的位置
while True:
# 从root开始对最大堆调整
child = 2 * root +1 #左(left)孩子的位置
if child > end:
break
# 找出两个child中较大的一个
if child + 1 <= end and arr[child] < arr[child + 1]: #如果左边小于右边
child += 1 #左右两孩子中选择较大者
if arr[root] < arr[child]:
# 最大堆小于较大的child, 交换顺序
tmp = arr[root]
arr[root] = arr[child]
arr[child]= tmp
root = child #
else:
# 无需调整的时候, 跳出循环
break

2.定义堆排序函数,传递待排数组,逐次遍历,

def heap_sort(arr):
# 从最后一个有子节点的孩子开始调整最大堆,不断的缩小调整的范围直到第一个元素
first = len(arr) // 2 -1
for i in range(first, -1, -1):
siftdown(arr, i, len(arr) - 1)
# 将最大的放到堆的最后一个, 堆-1, 继续调整排序
for end in range(len(arr) -1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
siftdown(arr, 0, end - 1)

验证堆排序算法:

def main():
array = [16,10,15,8,9,12,14,6]
print("原数组: ",array)
heap_sort(array)
print("排序后数组: ",array)
if __name__ == "__main__":
main()

执行结果:

【算法实践】他山之石,可以攻玉--利用完全二叉树快速实现堆排序

总结

一般需要排序的数据都存放于数组中,而堆排序使用了堆这个数据结构,相当于将堆嵌入到包含了序列的数组中,然后通过交换数组中的数据来进行排序,可以说是强行在数组中使用了堆结构。堆排序一开始需要将n个数据存进堆里,所需要时间为O(nlogn)。排序过程中,堆从空堆的状态开始,逐渐被数据填满,由于堆的高度小于log2n,所以插入1个数据所需要的时间是O(logn)。每轮取出最大的数据并重构堆需要的时间为O(logn),由于总共n轮,因此重构后排序的时间也是O(nlogn)。故整体看来堆排序的时间复杂度为O(nlogn),虽然堆排序整体运行效率不错,但是堆这个结构相对复杂,所以实现起来也较为困难。