堆是一种特殊的树形结构, 堆中的数据存储满足一定的堆序。堆排序是一种选择排序, 其算法复杂度, 时间复杂度相对于其他的排序算法都有很大的优势。
堆分为大头堆和小头堆, 正如其名, 大头堆的第一个元素是最大的, 每个有子结点的父结点, 其数据值都比其子结点的值要大。小头堆则相反。
我大概讲解下建一个树形堆的算法过程:
找到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官网
以上这篇python下实现二叉堆以及堆排序的示例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持。
标签:
堆排序,python实现
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件!
如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
金钱帮资源网 Copyright www.kbjia.com
暂无“python下实现二叉堆以及堆排序的示例”评论...
稳了!魔兽国服回归的3条重磅消息!官宣时间再确认!
昨天有一位朋友在大神群里分享,自己亚服账号被封号之后居然弹出了国服的封号信息对话框。
这里面让他访问的是一个国服的战网网址,com.cn和后面的zh都非常明白地表明这就是国服战网。
而他在复制这个网址并且进行登录之后,确实是网易的网址,也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情,因为以前都没有出现这样的情况,现在突然提示跳转到国服战网的网址,是不是说明了简体中文客户端已经开始进行更新了呢?
更新日志
2024年10月08日
2024年10月08日
- 洪荣宏.2010-上爱的人【华特】【WAV+CUE】
- 《大牌国语情歌 经典再现 深情对唱 2CD》[WAV/分轨][900MB]
- 《陈百强粉红色的一生精选 3CD》[FLAC/分轨][1.2GB]
- 《丁当 20首重量级歌曲 Fu Good 下一站天后 2CD》[WAV/分轨][650MB]
- 歌莉雅.2012-My.Voice.Story【环星】【FLAC分轨】
- 群星.1993-一曲成名·青春无悔【飞碟】【WAV+CUE】
- 刘德华.2000-爱无知(金装版)【NEWMELODY】【WAV+CUE】
- 许巍《时光漫步》1CD[FLAC/分轨][804.3MB]
- 群星《2024第一季度百度歌曲排行抖音榜top100》1CD[FLAC/分轨][2.3GB]
- 张柏芝《全新经验》[FLAC/分轨][450MB]
- 唐朝.2008-浪漫骑士【音乐家】【WAV+CUE】
- 张芸京.2016-失败的高歌【泡耳音乐】【WAV+CUE】
- 群星.1991-音乐工厂1·皇后大道东【音乐工厂】【WAV+CUE】
- 群星.1992-音乐工厂2·首都【音乐工厂】【WAV+CUE】
- 群星.1994-音乐工厂3·儿童乐园【音乐工厂】【WAV+CUE】