热线电话：13121318867

登录
首页精彩阅读Python实现堆排序的方法详解
Python实现堆排序的方法详解
2018-06-06
收藏

Python实现堆排序的方法详解

本文实例讲述了Python实现堆排序的方法。分享给大家供大家参考，具体如下：

堆排序作是基本排序方法的一种，类似于合并排序而不像插入排序，它的运行时间为O(nlogn)，像插入排序而不像合并排序，它是一种原地排序算法，除了输入数组以外只占用常数个元素空间。

堆（定义）：（二叉）堆数据结构是一个数组对象，可以视为一棵完全二叉树。如果根结点的值大于（小于）其它所有结点，并且它的左右子树也满足这样的性质，那么这个堆就是大（小）根堆。

我们假设某个堆由数组A表示，A[1]为树的根，给定某个结点的下标i，其父结点、左孩子、右孩子的下标都可以计算出来：

PARENT(i):
    return i/2
LEFT(i):
    return 2i
RIGHT(i):
    return 2i+1

堆排序Python实现

所谓堆排序的过程，就是把一些无序的对象，逐步建立起一个堆的过程。
下面是用Python实现的堆排序的代码：


defbuild_max_heap(to_build_list):
  """建立一个堆"""
  # 自底向上建堆
  foriinrange(len(to_build_list)/2-1,-1,-1):
    max_heap(to_build_list,len(to_build_list), i)
defmax_heap(to_adjust_list, heap_size, index):
  """调整列表中的元素以保证以index为根的堆是一个最大堆"""
  # 将当前结点与其左右子节点比较，将较大的结点与当前结点交换，然后递归地调整子树
  left_child=2*index+1
  right_child=left_child+1
  ifleft_child < heap_sizeandto_adjust_list[left_child] > to_adjust_list[index]:
    largest=left_child
  else:
    largest=index
  ifright_child < heap_sizeandto_adjust_list[right_child] > to_adjust_list[largest]:
    largest=right_child
  iflargest !=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)
defheap_sort(to_sort_list):
  """堆排序"""
  # 先将列表调整为堆
  build_max_heap(to_sort_list)
  heap_size=len(to_sort_list)
  # 调整后列表的第一个元素就是这个列表中最大的元素，将其与最后一个元素交换，然后将剩余的列表再调整为最大堆
  foriinrange(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)
  printto_sort_list




CDA数据分析师考试相关入口一览（建议收藏）：

▷ 想报名CDA认证考试，点击>>>   “CDA报名” 了解CDA考试详情；

▷ 想加入CDA考试题库，点击>>> “CDA题库” 了解CDA考试详情；

▷ 想学习CDA考试教材，点击>>> “CDA教材” 了解CDA考试详情；

▷ 想查询CDA考试成绩，点击>>> “CDA成绩” 了解CDA考试详情；

▷ 想了解CDA考试含金量，点击>>> “CDA含金量” 了解CDA考试详情；

▷ 想获取CDA考试时间/费用/条件/大纲/通过率，点击 >>>“CDA考试官网” 了解CDA考试详情；

数据分析咨询请扫描二维码

上一篇对区块链技术和智能合约安全的六种误读
下一篇聚类分析中几种算法的比较
CDA考试动态
CDA报考指南
热门栏目
最新资讯
更多
Copyright © 2015-present 北京国富如荷网络科技有限公司 All Rights Reserved.
京ICP备11001960号-9   京公网安备 11010802034615号   经营许可证编号：京B2-20210330
客服在线
立即咨询