首页 > 代码库 > [PY3]——heap模块 和 堆排序
[PY3]——heap模块 和 堆排序
heapify( )
heapify()函数用于将一个序列转化为初始化堆
nums=[16,7,3,20,17,8,-1]print(‘nums:‘,nums)show_tree(nums)nums: [16, 7, 3, 20, 17, 8, -1] 16 7 3 20 17 8 -1 ------------------------------------heapq.heapify(nums)print(‘nums:‘,nums)show_tree(nums)nums: [-1, 7, 3, 20, 17, 8, 16] -1 7 3 20 17 8 16 ------------------------------------
heappush( )
heappush()是实现将元素插入到堆的操作
heappush()操作前一定要先将序列初始化成堆！heappush是对于"堆"的操作！不然是没有意义
nums=[16,7,3,20,17,8,-1]print(nums)show_tree(nums) [16, 7, 3, 20, 17, 8, -1] 16 7 3 20 17 8 -1 ------------------------------------
heapq.heapify(nums)print(‘初始化成堆:‘,nums) show_tree(nums) 初始化成堆: [-1, 7, 3, 20, 17, 8, 16] -1 7 3 20 17 8 16 ------------------------------------for i in random.sample(range(1,8),2): print("本次push:",i) heapq.heappush(nums,i) print(nums) show_tree(nums) 本次push: 5 [-1, 5, 3, 7, 17, 8, 16, 20] -1 5 3 7 17 8 16 20 ------------------------------------ 本次push: 7 [-1, 5, 3, 7, 17, 8, 16, 20, 7] -1 5 3 7 17 8 16 20 7 ------------------------------------
heappop( )
heappop()是实现将元素删除出堆的操作
同样的操作前一定要先将序列初始化成堆，否则也没什么意义
nums=[16,7,3,20,17,8,-1]print(nums)show_tree(nums) [16, 7, 3, 20, 17, 8, -1] 16 7 3 20 17 8 -1 ------------------------------------heapq.heapify(nums)print(‘初始化成堆:‘,nums)show_tree(nums) 初始化成堆: [-1, 7, 3, 20, 17, 8, 16] -1 7 3 20 17 8 16 ------------------------------------
for i in range(0,2): print("本次pop：",heapq.heappop(nums)) print(nums) show_tree(nums) 本次pop： -1 [3, 7, 8, 20, 17, 16] 3 7 8 20 17 16 ------------------------------------ 本次pop： 3 [7, 16, 8, 20, 17] 7 16 8 20 17 ------------------------------------
nlargest( )/nsmallest( )
sorted(iterable, key=key, reverse=True)[:n]
- nlargest(n,iterable) 求序列iterable中的TopN | nsmallest(n,iterable) 求序列iterable中的BtmN
import heapqnums=[16,7,3,20,17,8,-1]print(heapq.nlargest(3,nums))print(heapq.nsmallest(3,nums))[20, 17, 16][-1, 3, 7]
- nlargest(n, iterable, key=lambda) | nsmallest(n, iterable, key=lambda) key接受关键字参数，用于更复杂的数据结构中
def print_price(dirt): for i in dirt: for x,y in i.items(): if x==‘price‘: print(x,y)portfolio = [ {‘name‘: ‘IBM‘, ‘shares‘: 100, ‘price‘: 91.1}, {‘name‘: ‘AAPL‘, ‘shares‘: 50, ‘price‘: 543.22}, {‘name‘: ‘FB‘, ‘shares‘: 200, ‘price‘: 21.09}, {‘name‘: ‘HPQ‘, ‘shares‘: 35, ‘price‘: 31.75}, {‘name‘: ‘YHOO‘, ‘shares‘: 45, ‘price‘: 16.35}, {‘name‘: ‘ACME‘, ‘shares‘: 75, ‘price‘: 115.65}]cheap=heapq.nsmallest(3,portfolio,key=lambda x:x[‘price‘])expensive=heapq.nlargest(3,portfolio,key=lambda y:y[‘price‘])print_price(cheap)print_price(expensive)price 16.35price 21.09price 31.75price 543.22price 115.65price 91.1
关于heap和heap sort
对于上面的nums=[16,7,3,20,17,8,-1]序列，图解了：
构造堆的操作（点击查看）
push堆的操作（点击查看）
pop堆的操作（点击查看）
参考文章
详解Python中heapq模块的用法(包括show_tree())
详解堆排序
浅谈算法和数据结构: 五 优先级队列与堆排序
[PY3]——heap模块 和 堆排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。