Python实现堆排序的方法详解

概述本文实例讲述了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,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,-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,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实现堆排序的方法详解全部内容，希望文章能够帮你解决Python实现堆排序的方法详解所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。