Python实现堆排序的方法详解
2019/7/13 23:33:26
本文主要是介绍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相关内容可查看本站专题:《Python正则表达式用法总结》、《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。
这篇关于Python实现堆排序的方法详解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python