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程序设计有所帮助。

赞 (0)

相关推荐

  • Python实现二叉堆

    Python实现二叉堆

    优先队列的二叉堆实现 在前面的章节里我们学习了"先进先出"(FIFO)的数据结构:队列(Queue).队列有一种变体叫做"优先队列"(Priority Queue).优先队列的出队(Dequeue)操作和队列一样,都是从队首出队.但在优先队列的内部,元素的次序却是由"优先级"来决定:高优先级的元素排在队首,而低优先级的元素则排在后面.这样,优先队列的入队(Enqueue)操作就比较复杂,需要将元素根据优先级尽量排到队列前面.我们将会发现,对于下一

  • python实现堆栈与队列的方法

    本文实例讲述了python实现堆栈与队列的方法.分享给大家供大家参考.具体分析如下: 1.python实现堆栈,可先将Stack类写入文件stack.py,在其它程序文件中使用from stack import Stack,然后就可以使用堆栈了. stack.py的程序: 复制代码 代码如下: class Stack():      def __init__(self,size):          self.size=size;          self.stack=[];         

  • python 实现堆排序算法代码

    复制代码 代码如下: #!/usr/bin/python import sys def left_child(node): return node * 2 + 1 def right_child(node): return node * 2 + 2 def parent(node): if (node % 2): return (i - 1) / 2 else: return (i - 2) / 2 def max_heapify(array, i, heap_size): l = left_c

  • Python记录详细调用堆栈日志的方法

    本文实例讲述了Python记录详细调用堆栈日志的方法.分享给大家供大家参考.具体实现方法如下: import sys import os def detailtrace(info): retStr = "" curindex=0 f = sys._getframe() f = f.f_back # first frame is detailtrace, ignore it while hasattr(f, "f_code"): co = f.f_code retSt

  • 详解Python中heapq模块的用法

    详解Python中heapq模块的用法

    heapq 模块提供了堆算法.heapq是一种子节点和父节点排序的树形数据结构.这个模块提供heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2].为了比较不存在的元素被人为是无限大的.heap最小的元素总是[0]. 打印 heapq 类型 import math import random from cStringIO import StringIO def show_tree(tree, total_width=36, fill=' '): ou

  • Python实现堆排序的方法详解

    Python实现堆排序的方法详解

    本文实例讲述了Python实现堆排序的方法.分享给大家供大家参考,具体如下: 堆排序作是基本排序方法的一种,类似于合并排序而不像插入排序,它的运行时间为O(nlogn),像插入排序而不像合并排序,它是一种原地排序算法,除了输入数组以外只占用常数个元素空间. 堆(定义):(二叉)堆数据结构是一个数组对象,可以视为一棵完全二叉树.如果根结点的值大于(小于)其它所有结点,并且它的左右子树也满足这样的性质,那么这个堆就是大(小)根堆. 我们假设某个堆由数组A表示,A[1]为树的根,给定某个结点的下标i,

  • python生成式的send()方法(详解)

    随便在网上找了找,感觉都是讲半天讲不清楚,这里写一下. def generator(): while True: receive=yield 1 print('extra'+str(receive)) g=generator() print(next(g)) print(g.send(111)) print(next(g)) 输出: 1 extra111 1 extraNone 1 为什么会这样呢,点进send就能看到一句话 send:Resumes the generator and "sen

  • Python中格式化format()方法详解

     Python中格式化format()方法详解 Python中格式化输出字符串使用format()函数, 字符串即类, 可以使用方法; Python是完全面向对象的语言, 任何东西都是对象; 字符串的参数使用{NUM}进行表示,0, 表示第一个参数,1, 表示第二个参数, 以后顺次递加; 使用":", 指定代表元素需要的操作, 如":.3"小数点三位, ":8"占8个字符空间等; 还可以添加特定的字母, 如: 'b' - 二进制. 将数字以2为基

  • 对python函数签名的方法详解

    函数签名对象,表示调用函数的方式,即定义了函数的输入和输出. 在Python中,可以使用标准库inspect的一些方法或类,来操作或创建函数签名. 获取函数签名及参数 使用标准库的signature方法,获取函数签名对象:通过函数签名的parameters属性,获取函数参数. # 注意是小写的signature from inspect import signature def foo(value): return value # 获取函数签名 foo_sig = signature(foo)

  • 把JSON数据格式转换为Python的类对象方法详解（两种方法）

    JOSN字符串转换为自定义类实例对象 有时候我们有这种需求就是把一个JSON字符串转换为一个具体的Python类的实例,比如你接收到这样一个JSON字符串如下: {"Name": "Tom", "Sex": "Male", "BloodType": "A", "Hobbies": ["篮球", "足球"]} 我需要把这个转换为具

  • 对python 自定义协议的方法详解

    前面说到最近在写python的一些东西,然后和另外一位小伙伴定义了协议,然后昨天我有一部分东西没理解对,昨天上午我自己重写了一遍接收和发送的全部逻辑,昨天下午补了压力测试的脚本,自测没问题之后告知联调的小伙伴. 结果上午还是出了一点问题,然后我们两对代码,他写了一个python的实现.还好最后我这边没问题.(我也害怕是我这边出问题啊,所以我自己的代码都自己检查了好几遍) 简单放一下他的实现: import struct import ctypes class E(Exception): def

  • Python底层封装实现方法详解

    这篇文章主要介绍了Python底层封装实现方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 事实上,python封装特性的实现纯属"投机取巧",之所以类对象无法直接调用私有方法和属性,是因为底层实现时,python偷偷改变了它们的名称. python在底层实现时,将它们的名称都偷偷改成了"_类名__属性(方法)名"的格式 class Person: def setname(self, name): if le

  • python集合删除多种方法详解

    python集合删除多种方法详解

    这篇文章主要介绍了python集合删除多种方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 删除指定的元素 A={'a','c','b','d','e'} print("原集合:",A) A.remove('a') # 不存在会报错 print("删除a后:",A) A.discard('b') # 不存在不会报错 print("删除b后:",A) A.pop() print("

  • Python实现括号匹配方法详解

    这篇文章主要介绍了python实现括号匹配方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 1.用一个栈[python中可以用List]就可以解决,时间和空间复杂度都是O(n) # -*- coding: utf8 -*- # 符号表 SYMBOLS = {'}': '{', ']': '[', ')': '(', '>': '<'} SYMBOLS_L, SYMBOLS_R = SYMBOLS.values(), SYMBOLS.ke

  • Python sep参数使用方法详解

    这篇文章主要介绍了Python sep参数使用方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Python中sep不是函数,它是print函数的一个参数,用来定义输出数据之间的间隔符号. 具体用法如下: 同时打印多个字符串的时候,每个字符串都会自动默认以空格作为每个字符串之间的间隔. print("abc", "uuu", "oop") # abc uuu oop 如果在多个字符串的最后

随机推荐