python下实现二叉堆以及堆排序的示例
作者:又见阿郎 时间:2023-02-19 16:44:23
堆是一种特殊的树形结构, 堆中的数据存储满足一定的堆序。堆排序是一种选择排序, 其算法复杂度, 时间复杂度相对于其他的排序算法都有很大的优势。
堆分为大头堆和小头堆, 正如其名, 大头堆的第一个元素是最大的, 每个有子结点的父结点, 其数据值都比其子结点的值要大。小头堆则相反。
我大概讲解下建一个树形堆的算法过程:
找到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官网
来源:http://www.cnblogs.com/zhiyong-ITNote/archive/2017/09/28/7608330.html
标签:堆排序,python,二叉堆
0
投稿
猜你喜欢
轻松掌握如何从命令行启动mysqld服务器
2008-12-31 15:47:00
Python包argparse模块常用方法
2023-04-03 13:30:58
Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法
2021-04-14 04:55:49
Springboot项目对数据库用户名密码实现加密过程解析
2024-01-19 23:02:04
Git 教程之基本操作详解
2023-08-04 08:04:20
深入了解Python二维直方图
2023-02-17 19:36:22
DBA_2PC_PENDING 介绍
2009-02-28 10:59:00
python numpy库之如何使用matpotlib库绘图
2023-02-07 22:22:24
python 绘制国旗的示例
2023-01-05 19:29:32
js实现登录注册框手机号和验证码校验(前端部分)
2023-09-13 02:41:37
Python中random模块用法实例分析
2023-01-02 19:40:25
PHP 实现一种多文件上传的方法
2024-05-03 15:07:11
SQL Server误区30日谈 第3天 即时文件初始化特性可以在SQL Server中开启和关闭
2024-01-16 18:38:28
echarts柱状堆叠图实现示例(图例和x轴都是动态的)
2024-04-29 13:21:03
解决go 生成的exe不在bin文件夹里的问题
2024-03-16 20:49:52
详解Django3中直接添加Websockets方式
2021-01-05 01:43:22
python之从文件读取数据到list的实例讲解
2021-11-11 08:04:26
深入了解Golang官方container/heap用法
2024-05-13 10:44:42
python numpy 常用随机数的产生方法的实现
2021-06-14 22:44:05
Python paramiko模块的使用示例
2021-05-12 20:30:00