Python实现堆排序的方法详解
作者:阿涵-_- 发布时间:2023-12-02 07:43:20
标签:Python,堆排序
本文实例讲述了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程序设计有所帮助。
0
投稿
猜你喜欢
- ps:不曾想还有那么好用的方法。汗一个先。Div即父容器不根据内容自适应高度,我们看下面的代码:<div id="main&
- 前言:HTML5和CSS3的时代到来了,新版2011版淘宝网首页已全部使用HTML5,拥抱变化才是王道。为之漫笔翻译的很好,看了一遍后,感觉
- 使用ASP实现网站的目录树数据库结构(共使用了两个表)1。tblCategory字段名 类型 Root&
- 表中主键必须为标识列,[ID] int IDENTITY (1,1)1.分页方案一:(利用Not In和SELECT TOP分页)语句形式:
- ASP正则表达式,RegExp对象提供简单的正则表达式支持功能。RegExp对象的用法: Function RegExpTest(
- IE独有属性AlphaImageLoader用于修正7.0以下版本中显示PNG图片的半透明效果。这个滤镜的问题在于浏览器加载图片时它会终止内
- 目录前言🎪 一、Python 关键字🎢 二、Python标识符🎠 2.1 在 Python 中创建标识符的指南🎡 2.2 测试标识符是否有效
- string iconv ( string $in_charset , string $out_charset , string $str
- 以前跟同事开玩笑时说过,我们遇到的用户在访谈测试过程中的表现基本上就三种类型,发泄型,赞美型和实话实说型。发泄型用户通常是在产品的使用过程中
- 非常好的一篇技术文档,翻译自Louis Lazaris 2009年9月15日发表的《The Z-Index CSS Property: A
- 本文实例讲述了Python字符串的全排列算法。分享给大家供大家参考,具体如下:题目描述输入一个字符串,按字典序打印出该字符串中字符的所有排列
- 语法: text-overflow : clip | ellipsis 参数: clip : 不显示省略标记(...),而是简单的裁切 el
- 上文:栅格:从混乱到秩序Jacci Howard Bear 的英文原文:http://desktoppub.about.com/od/gri
- SQL*Plus system/manager 2、显示当前连接用户 SQL> show user 3、查看系统拥有哪些用户 SQL&
- 本文实例讲述了php中对象引用和复制。分享给大家供大家参考,具体如下:引用$tv2 = $tv1;或者$tv2 = &$tv1;以上
- 本文主要是基于Python Opencv 实现的图像分割,其中使用到的opencv的函数有:使用 OpenCV 函数 cv::filter2
- 摘要:本文主要就数据库恢复与系统任务的调度,在结合一般性的数据库后台处理的经验上,提出较为实用而新颖的解决方法,拓宽了数据库后台开发的思路。
- 目录:分析和设计组件编码实现和算法用 Ant 构建组件测试 JavaScript 组件话说上期我们讨论了队列管理组件的设计,并且给它取了个响
- 初学python,抓取搜狗微信公众号文章存入mysqlmysql表:代码:import requestsimport jsonimport
- 本文深入分析了Symfony控制层。分享给大家供大家参考,具体如下:Symfony中控制层包含了连接业务逻辑与表现的代码,控制层为不同的使用