python下实现二叉堆以及堆排序

堆是一种特殊的树形结构, 堆中的数据存储满足一定的堆序。堆排序是一种选择排序, 其算法复杂度, 时间复杂度相对于其他的排序算法都有很大的优势。

堆分为大头堆和小头堆, 正如其名, 大头堆的第一个元素是最大的, 每个有子结点的父结点, 其数据值都比其子结点的值要大。小头堆则相反。

我大概讲解下建一个树形堆的算法过程:
找到N/2 位置的数组数据, 从这个位置开始, 找到该节点的左子结点的索引, 先比较这个结点的下的子结点, 找到最大的那个, 将最大的子结点的索引赋值给左子结点, 然后将最大的子结点和父结点进行对比, 如果比父结点大, 与父节点交换数据。当然, 我只是大概说了下实现, 在此过程中, 还需要考虑结点不存在的情况。看下代码:

# 构建二叉堆
def binaryHeap(arr, lenth, m):
temp = arr[m] # 当前结点的值
while(2*m+1 < lenth):
lchild = 2*m+1
if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:
lchild = lchild + 1
if temp < arr[lchild]:
arr[m] = arr[lchild]
else:
break
m = lchild
arr[m] = temp def heapsort(arr, length):
i = int(len(arr)/2)
while(i >= 0):
binaryHeap(arr, len(arr), i)
i = i - 1 print("二叉堆的物理顺序为:")
print(arr) # 输出二叉堆的物理顺序 if __name__ == '__main__':
arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98] heapsort(arr, len(arr))

堆排序过程就是依次将最后的结点与首个节点进行对比交换:

# 构建二叉堆
def binaryHeap(arr, lenth, m):
temp = arr[m] # 当前结点的值
while(2*m+1 < lenth):
lchild = 2*m+1
if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:
lchild = lchild + 1
if temp < arr[lchild]:
arr[m] = arr[lchild]
else:
break
m = lchild
arr[m] = temp def heapsort(arr, length):
i = int(len(arr)/2)
while(i >= 0):
binaryHeap(arr, len(arr), i)
i = i - 1 print("二叉堆的物理顺序为:")
print(arr) # 输出二叉堆的物理顺序 i = length-1
while(i > 0):
arr[i], arr[0] = arr[0], arr[i] # 变量交换
binaryHeap(arr, i, 0)
i = i - 1560 def pop(arr):
first = arr.pop(0)
return first if __name__ == '__main__':
arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98] heapsort(arr, len(arr)) print("堆排序后的物理顺序")
print(arr) # 输出经过堆排序之后的物理顺序 data = pop(arr)
print(data) print(arr)

堆排序的过程就是将原有的二叉堆(我这里实现大顶堆, 即第一个元素是最大的,父结点的数据值大于子结点)的第一个元素放到堆尾,随后就是将剩下的结点再重新构成二叉堆(依旧是大顶堆),因此只要递归原二叉堆实现过程就行。

python封装了一个堆模块, 我们使用该模块可以很高效的实现一个优先队列:

import heapq

class Item:
def __init__(self, name):
self.name = name def __repr__(self):
return 'Item({!r})'.format(self.name) class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0 def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item)) # 存入一个三元组
self._index += 1 def pop(self):
return heapq.heappop(self._queue)[-1] # 逆序输出 if __name__ == '__main__':
p = PriorityQueue()
p.push(Item('foo'), 1)
p.push(Item('bar'), 5)
p.push(Item('spam'), 4)
p.push(Item('grok'), 1) print(p.pop())
print(p.pop())

具体请看heapq官网

最新文章

  1. C#-WebForm-Repeater-重复器
  2. c#获取下载路径
  3. wpf 任务栏闪烁
  4. ###《More Effective C++》- 基础议题
  5. iis7.5 应用程序池 经典模式和集成模式的区别
  6. WebApp之Meta标签 (关闭自动识别数字为电话号码或邮箱之类)
  7. Tuning Radio Resource in an Overlay Cognitive Radio Network for TCP: Greed Isn’t Good
  8. 一个Java项目的学习
  9. zepto 获取checked selected元素
  10. 工具类总结---(三)---MD5加密
  11. 几大排序思想(由javascript编写)
  12. 理解Babel是如何编译JS代码的及理解抽象语法树(AST)
  13. VMware下安装centos7及网络配置
  14. WebStorm重复代码快捷表达
  15. iOS更换科大讯飞的key
  16. ModelValidator基于元数据的验证
  17. 使用JSR-303进行后台数据校验
  18. andriod创建用户界面(1)
  19. python提取相对路径
  20. Linux系统初学-第一课 虚拟机安装CentOS6.5以及Root密码找回

热门文章

  1. HTML5在VS2010中的智能提示
  2. 如何在windows 10 x64安装佳能 CP900 驱动
  3. Laravel 5 数据库迁移文件示例
  4. php笔试题(1)--转载
  5. Ubuntu升级内核
  6. C++调用WebService服务问题总结
  7. MVC 中使用log4net 打印重复日志解决方法
  8. [置顶] 【玩转cocos2d-x之七】场景类CCScene和布景类CCLayer
  9. vc实现ping
  10. Ambari源代码分析之Resource.Type与ResourceProvider相应关系
  11. Go 语言指针
  12. 【SSH系列】Hibernate映射-- 多对一单向关联映射
  13. 【Maven】---Nexus私服配置Setting和Pom
  14. java 各种循环遍历
  15. Git/Github的使用并与Eclipse整合(zz)
  16. Python:基础知识
  17. 【Java】Java-XML解析利器-SAX-高性能-易用
  18. Cocos开发中可能会遇到的问题
  19. Jmeter--正则表达式提取器
  20. 【刷题】BZOJ 2049 [Sdoi2008]Cave 洞穴勘测