开发者社区> 登天蚂蚁> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

排序算法(五):堆排序

简介: 从二叉搜索树和平衡二叉树的介绍中,可以发现二叉树这种结构具有一个很好的特性,当有序的二叉树构造完成之后,更改树中节点后,只需要 的时间复杂度即可将二叉树重新调整为有序状态。
+关注继续查看
img_695a67d3fb3b6f20f1c8857443c39b20.jpe

二叉搜索树平衡二叉树的介绍中,可以发现二叉树这种结构具有一个很好的特性,当有序的二叉树构造完成之后,更改树中节点后,只需要 O(log_2N) 的时间复杂度即可将二叉树重新调整为有序状态。若构造出一种具有特殊节点顺序的二叉树,使得每次对二叉树执行插入或删除节点操作后,都调整保持二叉树根节点的值为树中节点的极值,则 N 个元素的集合,构造出这种二叉树后,只需要对树执行 N-1 次的取根节点操作,即可获得一个有序序列。整个取节点加调整操作的时间复杂度为 O(Nlog_2N),若构造这种二叉树的时间复杂度不高于 O(Nlog_2N),则采用构造这种二叉树的方式来完成排序的时间复杂度为 O(Nlog_2N)

堆定义

上面提到的利用具有特殊节点顺序的二叉树完成排序的方式,就是堆排序。这里所说的节点顺序是指:树中每个节点的值都不小于(不大于)它的子节点值。堆描述的是一颗完全二叉树,在对数组进行排序的过程中,并不是真的构建一个二叉树结构,只是将数组中元素下标映射到完全二叉树,利用元素下标来表示父节点和子节点关系。

img_5bd8854c527f02ea0da37d88a3821b64.png
list type
img_df79a9c5e9889a52c19cfd95ee0201a7.png
tree type

通过以上两张图可知,堆中父子节点的下标关系为:

  • 下标为 i 的节点,其左子节点下标为 2*i+1
  • 下标为 i 的节点,其右子节点下标为 2*i+2
  • 下标为 i 的节点,其父节点下标为 \lfloor {\frac {i-1} 2} \rfloor(i\ge1)

算法过程

以递增排序为例,集合初始为待排序集合,已排序集合为空

  1. 构造最大堆,即调整待排序集合,使得元素映射出的完全二叉树,满足每个节点元素值都不小于其子节点值
  2. 替换待排序集合中第一个元素和最后一个元素值,即在待排序集合映射出的完全二叉树上,将根节点值和树中最下面一层、最右边的节点值进行替换
  3. 调整堆结构使其满足节点大小顺序,标记待排序集合最后一个元素为已排序
  4. 重复步骤2, 3,直到待排序集合只有一个元素

演示示例

调整为最大堆结构

要保证每个节点的值不小于其左右子节点的值,只需要从后往前遍历集合中每个具有子节点的节点,使得其节点值不小于左右子节点的值即可(递归与子节点进行比较)。已知下标为 i 的节点,其父节点下标为 \lfloor {\frac {i-1} 2} \rfloor(i\ge1),所以具有 N 个元素的集合,起始遍历节点的下标为 \lfloor { {\frac {N} 2} -1} \rfloor(i\ge1)

起始待调整元素下标为 4,即值为 2 的节点

img_749ba0702a8a5c5210b43e2dd59aed1f.png

1 次调整后,下一个待调整元素下标为 3,即值为 0 的节点

img_970edc60029ddbbc5062fd858d695e19.png

2 次调整后,下一个待调整元素下标为 2,即值为 4 的节点

img_779b7679430a5596c870955958180ae3.png

3 次调整后,下一个待调整元素下标为 1,即值为 3 的节点。这里注意,节点 3 与子节点 9 比较并交换后,需要递归与子节点进行比较,直到值不小于子节点值

img_545d446bb2acefd496f63f576471323a.png
step_1
img_921bfb0cb30ca6a5fe0651b255eacf8e.png
step_2

4 次调整后,下一个待调整元素下标为 0,即值为 5 的节点。同样涉及递归操作

img_6e34e4191f7f732e2ba4da7c462cc9f9.png

5 次调整后,当前结构即为最大堆

img_f7b7dbd1db9f9e7c64ac0235bb497367.png
调整代码
def transformToHeap(arr, index, end):
    targetIndex, leftChildIndex, rightChildIndex = index, 2 * index + 1, 2 * index + 2
    if leftChildIndex < end and arr[leftChildIndex] > arr[targetIndex]:
        targetIndex = leftChildIndex
    if rightChildIndex < end and arr[rightChildIndex] > arr[targetIndex]:
        targetIndex = rightChildIndex
    if not targetIndex == index:
        arr[index], arr[targetIndex] = arr[targetIndex], arr[index]
        transformToHeap(arr, targetIndex, end)

代码中声明 targetIndex 用于指向根节点、左右子节点中的最大节点,若需要替换节点值,则递归调整替换后的根节点和其左右子节点。end 变量用于标志待排序集合的边界。

迭代获取堆顶元素

重复将待排序集合首元素和尾元素进行替换,标记替换后的尾元素为已排序,并调整堆结构使其重新成为最大堆。

起始待替换根节点为 9,第 1 次替换并调整后结构后(调整过程上面已列出)
待排序集合:[8, 7, 4, 6, 5, 1, 2, 3, 0]
已排序集合:[9]

img_ac4dde1bc301591ca58b699bd7078e39.png

下一个待替换根节点为 8,第 2 次替换并调整后结构后
待排序集合:[7, 6, 4, 3, 5, 1, 2, 0]
已排序集合:[8, 9]

img_92cf77e0c702b69d79c8ea29c830e48f.png

...
...
...

下一个待替换根节点为 0,第 9 次替换并调整后结构后
待排序集合:[0]
已排序集合:[1, 2, 3, 4, 5, 6, 7, 8, 9]

img_2283344bc3fb486f4e37eaf4f23f4030.png

观察以上过程可知,每次排序后待排序集合元素数减一。N 个元素的序列,经过 N-1 次排序后,待排序集合元素数为一,即完成排序。

迭代操作代码
def heapSort(arr):
    index = len(arr) // 2 - 1
    while index >= 0:
        transformToHeap(arr, index, len(arr))  # transform arr to heap arr
        index = index - 1
    num = 1
    while num < len(arr):
        arr[0], arr[-num] = arr[-num], arr[0]
        transformToHeap(arr, 0, len(arr) - num)  # transform arr to heap arr
        num = num + 1

代码中第一个循环为构造最大堆,第二个循环为替换待排序集合首尾元素,并调整最大堆。

算法分析

堆排序是一种不稳定排序算法,对于 N 个元素的序列,构造堆过程,需要遍历的元素次数为 O(N),每个元素的调整次数为 O(log_2N),所以构造堆复杂度为 O(Nlog_2N)。迭代替换待排序集合首尾元素的次数为 O(N),每次替换后调整次数为 O(log_2N),所以迭代操作的复杂度为 O(Nlog_2N)。由此可知堆排序的时间复杂度为 O(Nlog_2N),排序过程属于原地排序,不需要额外的存储空间,所以空间复杂度为 O(1)

github 链接:堆排序

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
排序:选择排序(算法)
排序就是算法。   选择排序(Selection sort)是一种简单直观的排序算法。 选择排序是不稳定的排序方法。   eg:序列[9,9, 1]第一次就将第一个[9]与[1]交换,导致第一个9挪动到第二个9后面 Note:一般面试的时候才会用到选择、冒泡排序。
55 0
排序算法:选择排序
排序算法:选择排序
41 0
算法-选择排序
选择排序是一种排序算法,它在每次迭代中从未排序列表中选择最小元素,并将该元素放在未排序列表的开头。
48 0
排序算法
排序之PHP实现
662 0
排序算法:选择排序
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
688 0
堆排序算法---属于选择排序
1.堆   堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:   Key[i]=key[2i+2]   即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。   堆分为大顶堆和小顶堆,满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足 Ke...
565 0
+关注
登天蚂蚁
相信量变引发质变,相信厚积薄发
30
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载