Python实现堆排序的方法详解

yipeiwu_com5年前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使用selenium实现批量文件下载

python使用selenium实现批量文件下载

背景 实现需求:批量下载联想某型号的全部驱动程序。 一般在做网络爬虫的时候,都是保存网页信息为主,或者下载单个文件。当涉及到多文件批量下载的时候,由于下载所需时间不定,下载的文件名不定,...

使用Python向C语言的链接库传递数组、结构体、指针类型的数据

使用python向C语言的链接库传递数组、结构体、指针类型的数据 由于最近的项目频繁使用python调用同事的C语言代码,在调用过程中踩了很多坑,一点一点写出来供大家参考,我们仍然是使用...

Python2.5/2.6实用教程 入门基础篇

起步走 复制代码 代码如下: #! /usr/bin/python a=2 b=3 c="test" c=a+b print "execution result: %i"%c 知识点...

Pytorch修改ResNet模型全连接层进行直接训练实例

之前在用预训练的ResNet的模型进行迁移训练时,是固定除最后一层的前面层权重,然后把全连接层输出改为自己需要的数目,进行最后一层的训练,那么现在假如想要只是把 最后一层的输出改一下,不...

Python Pandas批量读取csv文件到dataframe的方法

Python Pandas批量读取csv文件到dataframe的方法

PYTHON Pandas批量读取csv文件到DATAFRAME 首先使用glob.glob获得文件路径。然后定义一个列表,读取文件后再使用concat合并读取到的数据。 #读取数...