动画 | 什么是堆排序?

Docker swarm实战总结,Docker管理工具-Swarm,docker-compose编排参数详解

回顾一下我们学过的选择排序,在无序区找到一个最小(大)的元素需要比较n-1次,找到第二小的元素需要比较n-2次,直到最后比较1次。而堆排序因为二叉堆的性质,堆顶就是最大的元素,查找次数只有一次,但是将无序转成有序中间还需要一个预处理过程:构造堆有序。

堆有序并不代表数组有序,堆有序是满足二叉堆性质的:

1.父节点的键值总是优先于任何一个子节点的键值;

2.左右子树都是一个二叉堆。

所以堆排序分为两个阶段,构造堆有序和下沉排序阶段。

构造堆有序阶段是将原始数据重新组织安排到一个二叉堆中,堆有序就是一棵二叉树的每个节点都优先于它的两个子节点,不代表数组有序;

下沉排序阶段是将二叉堆中取出优先级高的直至取出所有元素,得到数组有序结果。

构造堆有序的方式有两种,一种是上浮,另一种是下沉。这里以最大堆为例。

自低向上的堆有序化(上浮)

上浮是某节点与其父节点的比较,如果某节点比其父节点要大,就通过交换的方式进行修复堆。如果这个节点仍然比现在的父节点还大,可以通过循环的方式进行修复堆,直到遇到更大的父节点。

那从哪个节点开始呢?

WPF之图片处理系列

如果从数组最后一个节点进行开始上浮操作,它的父节点和祖父节点大小关系是不确定的,如果它的祖父节点比它父节点小,并不能保证整个完全二叉树能够二叉堆化。

所以从根节点的左孩子开始进行,数组下标为1开始,进行自底向上的堆有序化。在循环进行比较的时候会发现,这个节点已经进行过修复堆了,所以当上浮操作不再交换的时候可以做一个标记,截止进行比较。

如果能够合理优化的话,在时间上的消耗有可能要比下沉阶段的还要少。

动画

Code

动画 | 什么是堆排序?

Result

初始状态 [13, 9, 15, 11, 3, 7, 17, 5, 1]
交换 [15, 9, 13, 11, 3, 7, 17, 5, 1]
交换 [15, 11, 13, 9, 3, 7, 17, 5, 1]
交换 [15, 11, 17, 9, 3, 7, 13, 5, 1]
交换 [17, 11, 15, 9, 3, 7, 13, 5, 1]
[17, 11, 15, 9, 3, 7, 13, 5, 1]

自顶向下的堆有序化(下沉)

下沉是当前节点和左右孩子三者之中的比较,在整个进行自顶向下堆有序化的过程中,它是从非叶子节点开始的,即数组最后一个节点的父节点。

动画

Code

动画 | 什么是堆排序?

Result

初始状态 [13, 9, 15, 11, 3, 7, 17, 5, 1]
交换 [13, 9, 17, 11, 3, 7, 15, 5, 1]
交换 [13, 11, 17, 9, 3, 7, 15, 5, 1]
交换 [17, 11, 13, 9, 3, 7, 15, 5, 1]
交换 [17, 11, 15, 9, 3, 7, 13, 5, 1]
[17, 11, 15, 9, 3, 7, 13, 5, 1]

下沉排序

堆排序的主要工作还是在第二阶段完成的,下沉排序。这里我们将堆中最大的元素取出,和数组最后一个元素做交换,数组可操作的长度也相应的缩小一个位置。然后从堆顶开始进行下沉操作,无论循环多次都是从堆顶开始,直到数组可操作的长度最后为1。

动画

Code

动画 | 什么是堆排序?

Result

初始状态 [13, 9, 15, 11, 3, 7, 17, 5, 1]
堆有序
交换 [13, 9, 17, 11, 3, 7, 15, 5, 1]
交换 [13, 11, 17, 9, 3, 7, 15, 5, 1]
交换 [17, 11, 13, 9, 3, 7, 15, 5, 1]
交换 [17, 11, 15, 9, 3, 7, 13, 5, 1]
排序
交换 [15, 11, 1, 9, 3, 7, 13, 5, 17]
交换 [15, 11, 13, 9, 3, 7, 1, 5, 17]
交换 [13, 11, 5, 9, 3, 7, 1, 15, 17]
交换 [13, 11, 7, 9, 3, 5, 1, 15, 17]
交换 [11, 1, 7, 9, 3, 5, 13, 15, 17]
交换 [11, 9, 7, 1, 3, 5, 13, 15, 17]
交换 [9, 5, 7, 1, 3, 11, 13, 15, 17]
交换 [7, 5, 3, 1, 9, 11, 13, 15, 17]
交换 [5, 1, 3, 7, 9, 11, 13, 15, 17]
[1, 3, 5, 7, 9, 11, 13, 15, 17]

Rabbit安装(单机及集群,阿里云)

© 版权声明
THE END
喜欢就支持一下吧
点赞0
分享