python-堆-heapd
2021/11/14 22:12:28
本文主要是介绍python-堆-heapd,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
python-heapd
目录- python-heapd
- heapq堆的常用方法
- 堆类型的最大和最小值
- heapq.nlargest(n,heap)
- heapq.nsmallest(n,heap)
- heapq.heapify(list)
- heapq.heappop(heap)
- heapq.heappush(heap, item)
- heapq.heapreplace(heap.item)
- heapq.heappushpop(list, item)
- heapq.merge(…)
- 堆类型的最大和最小值
- 使用heapq编写优先级队列
- heapq堆的常用方法
堆是非线性的树形的数据结构,有两种堆,最大堆与最小堆(heapq库中的堆默认是最小堆)
最大堆,树种各个父节点的值总是大于或等于任何一个子节点的值。
最小堆,树种各个父节点的值总是小于或等于任何一个子节点的值。
一般使用二叉树实现优先队列,算法复杂度logN
heapq堆的常用方法
堆类型的最大和最小值
怎样从一个集合中获得最大或者最小的 N 个元素列表
heapq.nlargest(n,heap)
- input: n个数,heap 堆数据
- return 最大最小元素列表
import heapq numbers = [1, 4, 2, 100, 20, 50, 32, 200, 150, 8] print(heapq.nlargest(4, numbers)) # 输出:[200, 150, 100, 50]
import heapq 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} ] expensive = heapq.nlargest(2, portfolio, key=lambda s: s['price']) print(expensive) # [{'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'ACME', 'shares': 75, 'price': 115.65}]
heapq.nsmallest(n,heap)
lis=[3, 5, 5, 9, 6, 6, 8, 99] res=heapq.nsmallest(3,lis) print(res) # [3,5,5]
heapq.heapify(list)
直接将列表就地转换为堆,重新排列列表中的项,无返回值
- input: list >> heap
- return None
堆最有趣的属性是它的最小元素始终是第一个元素:heap [0]
numbers = [10, 4, 2, 100, 20, 50, 32, 200, 150, 8] heap=heapq.heapify(numbers) #将列表就地转换为堆 print(heap) print(numbers) # None # [2, 4, 10, 100, 8, 50, 32, 200, 150, 20] # 堆的第一个元素一定是最小的那个值
heapq.heappop(heap)
删除并返回最小值,堆的特征是heap[0]永远是最小的元素
弹出并返回堆中的最小项,保持堆不变。如果堆是空的,则引发IndexError
numbers = [10, 4, 2, 100, 20, 50, 32, 200, 150, 8] heapq.heappop(numbers) # 删除最小的值最返回:2 print(numbers) # 输出: [4, 8, 10, 100, 20, 50, 32, 200, 150] heapq.heappop(numbers) # 删除最小的值最返回:4 print(numbers) # 输出: [8, 20, 10, 100, 150, 50, 32, 200]
heapq.heappush(heap, item)
向 heap 压入一个值
注:heap为定义堆,item增加的元素
import heapq h = [] heapq.heappush(h,2) print(h) # [2]
heapq.heapreplace(heap.item)
先删除最小值,再添加新值
先 pop 最小元素,再压入 item,相当于先调用 heappop() 再调用heappush();
先删除最小元素值,再添加新的元素值
list=[2, 5, 3, 9, 6, 5, 8, 99] hppop=heapq.heapreplace(list,6) print(hppp) print(list) # 2 # [3, 5, 5, 9, 6, 6, 8, 99] list=[3, 5, 5, 9, 6, 6, 8, 99] hppop=heapq.heapreplace(list,1) print(hppop) print(list) # 1 # [3, 5, 5, 9, 6, 6, 8, 99]
heapq.heappushpop(list, item)
将 item 放入堆中,然后弹出并返回 heap 的最小元素, 该函数比先调用 heappush() 再调用 heappop() 效率更高
先添加新元素,再删除最小元素
list=[2, 5, 3, 9, 6, 5, 8, 99] hppop=heapq.heappushpop(list,6) print(hppp) print(list) # 2 # [3, 5, 5, 9, 6, 6, 8, 99] list=[3, 5, 5, 9, 6, 6, 8, 99] hppop=heapq.heappushpop(list,1) print(hppop) print(list) # 1 # [3, 5, 5, 9, 6, 6, 8, 99]
heapq.merge(…)
返回顺序迭代器
import heapq a = [1, 3, 7, 10] b = [2, 5, 6, 11] for c in heapq.merge(a, b): print(c) 1 2 3 5 6 7 10
使用heapq编写优先级队列
class PriorityQueue: def __init__(self): self.__queue = [] self.__index = 0 def push(self, item, priority): heapq.heappush(self.__queue, (-priority, self.__index, item)) # 第一个参数:添加进的目标序列 # 第二个参数:将一个元组作为整体添加进序列,目的是为了方便比较 # 在priority相等的情况下,比较_index # priority为负数使得添加时按照优先级从大到小排序,因为堆排序的序列的第一个元素永远是最小的 self.__index += 1 def pop(self): # 返回按照-priority 和 _index 排序后的第一个元素(是一个元组)的最后一个元素(item) return heapq.heappop(self.__queue)[-1] q = PriorityQueue() q.push("bar", 2) q.push("foo", 1) q.push("gork", 3) q.push("new", 1) print(q.pop()) print(q.pop()) print(q.pop()) print(q.pop()) """ gork # 优先级最高 bar # 优先级第二 foo # 优先级与new相同,比较index,因为先加入,index比new小,所以排在前面 new """
有 1000 个无序的整数,希望使用最快的方式找出前 50 个最大的
import heapq def heapsort(data, hp_size=3): h = [] for i in range(len(data)): if i >= hp_size: heapq.heappushpop(h, data[i]) #先放入值,在弹出 else: heapq.heappush(h, data[i]) return [heapq.heappop(h) for _ in range(len(h))] res = heapsort([6,2,1,-4,9,4,0]) print(res)
这篇关于python-堆-heapd的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python