Python实现堆排序的方法详解
作者:阿涵-_- 时间:2023-12-02 07:43:20
本文实例讲述了Python实现堆排序的方法。分享给大家供大家参考,具体如下:
堆排序作是基本排序方法的一种,类似于合并排序而不像插入排序,它的运行时间为O(nlogn),像插入排序而不像合并排序,它是一种原地排序算法,除了输入数组以外只占用常数个元素空间。
堆(定义):(二叉)堆数据结构是一个数组对象,可以视为一棵完全二叉树。如果根结点的值大于(小于)其它所有结点,并且它的左右子树也满足这样的性质,那么这个堆就是大(小)根堆。
我们假设某个堆由数组A表示,A[1]为树的根,给定某个结点的下标i,其父结点、左孩子、右孩子的下标都可以计算出来:
PARENT(i):
return i/2
LEFT(i):
return 2i
RIGHT(i):
return 2i+1
堆排序Python实现
所谓堆排序的过程,就是把一些无序的对象,逐步建立起一个堆的过程。
下面是用Python实现的堆排序的代码:
def build_max_heap(to_build_list):
"""建立一个堆"""
# 自底向上建堆
for i in range(len(to_build_list)/2 - 1, -1, -1):
max_heap(to_build_list, len(to_build_list), i)
def max_heap(to_adjust_list, heap_size, index):
"""调整列表中的元素以保证以index为根的堆是一个最大堆"""
# 将当前结点与其左右子节点比较,将较大的结点与当前结点交换,然后递归地调整子树
left_child = 2 * index + 1
right_child = left_child + 1
if left_child < heap_size and to_adjust_list[left_child] > to_adjust_list[index]:
largest = left_child
else:
largest = index
if right_child < heap_size and to_adjust_list[right_child] > to_adjust_list[largest]:
largest = right_child
if largest != index:
to_adjust_list[index], to_adjust_list[largest] = \
to_adjust_list[largest], to_adjust_list[index]
max_heap(to_adjust_list, heap_size, largest)
def heap_sort(to_sort_list):
"""堆排序"""
# 先将列表调整为堆
build_max_heap(to_sort_list)
heap_size = len(to_sort_list)
# 调整后列表的第一个元素就是这个列表中最大的元素,将其与最后一个元素交换,然后将剩余的列表再调整为最大堆
for i in range(len(to_sort_list) - 1, 0, -1):
to_sort_list[i], to_sort_list[0] = to_sort_list[0], to_sort_list[i]
heap_size -= 1
max_heap(to_sort_list, heap_size, 0)
if __name__ == '__main__':
to_sort_list = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
heap_sort(to_sort_list)
print to_sort_list
希望本文所述对大家Python程序设计有所帮助。
标签:Python,堆排序
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Python实现的批量修改文件后缀名操作示例
2021-08-28 08:34:58
![](https://img.aspxhome.com/file/2023/3/101643_0s.png)
浅谈python中拼接路径os.path.join斜杠的问题
2023-08-21 23:41:23
python 发送邮件的示例代码(Python2/3都可以直接使用)
2023-05-12 08:53:56
程序员的七种武器
2008-11-01 17:13:00
关于Pycharm配置翻译插件Translation报错更新TTK失败不能使用的问题
2023-08-22 05:02:17
![](https://img.aspxhome.com/file/2023/6/135236_0s.png)
Python Pandas数据中对时间的操作
2023-06-10 00:50:57
![](https://img.aspxhome.com/file/2023/5/130795_0s.png)
Python Matplotlib中使用plt.savefig存储图片的方法举例
2021-11-19 14:08:55
![](https://img.aspxhome.com/file/2023/1/79431_0s.png)
Mysql IO 内存方面的优化
2024-01-15 11:55:18
![](https://img.aspxhome.com/file/2023/4/124524_0s.png)
win10环境下配置vscode python开发环境的教程详解
2022-09-06 21:19:49
![](https://img.aspxhome.com/file/2023/1/71991_0s.png)
Python高级特性之切片迭代列表生成式及生成器详解
2021-06-25 23:10:13
Python游戏开发之魔塔小游戏的实现
2022-08-26 16:14:35
![](https://img.aspxhome.com/file/2023/6/66426_0s.gif)
php之二维数组排序问题
2023-07-15 06:44:42
SQL Server表空间碎片化回收的实现
2024-01-21 14:08:43
Vue实现自定义下拉菜单功能
2024-05-09 15:19:14
![](https://img.aspxhome.com/file/2023/3/126473_0s.png)
Python中创建对象列表的实现示例
2023-08-15 07:20:35
置信椭圆原理以及椭圆图形绘制方式
2021-04-24 04:25:04
![](https://img.aspxhome.com/file/2023/4/97034_0s.png)
Mysql服务器的安装配置与启动关闭方法详解
2024-01-28 05:10:26
![](https://img.aspxhome.com/file/2023/1/69151_0s.png)
Vue3 组件库的环境配置搭建过程
2024-04-30 10:19:58
![](https://img.aspxhome.com/file/2023/6/130286_0s.png)
vue使用ElementUI时导航栏默认展开功能的实现
2024-05-09 15:18:14
python队列原理及实现方法示例
2022-10-08 20:53:09