>[success] # 一些常用的heapq熟悉 >[danger] ##### heapify -- 将列表转换成堆 堆的重要特性就是第0个元素总是最小 ~~~ import heapq nums = [23,3,5,6,7,-1,5,6,1,10] # 为了不破坏原来的list集合所以特意重新转换一下 heap = list(nums) heapq.heapify(heap) print(heap) 打印结果： [-1, 1, 5, 3, 7, 5, 23, 6, 6, 10] ~~~ >[danger] ##### heappop -- 删除最小值 这个 运行速度O（logN）也就是堆越大，使用此方法的运行速度越慢 ~~~ import heapq nums = [23,3,5,6,7,-1,5,6,1,10] heap = list(nums) # 先转换成堆然后再删除 heapq.heapify(heap) # 删除第0个元素 print(heapq.heappop(heap)) 打印结果： -1 ~~~ >[danger] ##### heapreplace -- 弹出最小值，然后将新参数加入 只弹出未添加时最小值，下面的例子当加入的是-3，弹出的是-1 ~~~ import heapq nums = [23,3,5,6,7,-1,5,6,1,10] heap = list(nums) # 先转换成堆然后再删除 heapq.heapify(heap) heapq.heapreplace(heap,66) print(heap) 打印结果： [1, 3, 5, 6, 7, 5, 23, 6, 66, 10] ~~~ >[danger] ##### heappushpop -- 弹出最小值，然后将新参数加入 只弹出添加后最小值，下面的例子当加入的是-3，弹出的是-3 ~~~ import heapq nums = [23,3,5,6,7,-1,5,6,1,10] heap = list(nums) # 先转换成堆然后再删除 heapq.heapify(heap) heapq.heappushpop(heap,66) print(heap) 打印结果： [1, 3, 5, 6, 7, 5, 23, 6, 66, 10] ~~~ >[danger] ##### heappush 添加元素 ~~~ import heapq nums = [23,3,5,6,7,-1,5,6,1,10] heap = list(nums) # 先转换成堆然后再删除 heapq.heapify(heap) heapq.heappush(heap,66) print(heap) ~~~ >[success] # 实现优先级案例 ~~~ 1. 要有能储存的堆，也就是列表类型 2. 要设置优先级 3. 要设置插入的顺序 ~~~ >[danger] ##### 案例 >实现一个队列，能够根据优先级来对元素排序，每次返回优先级最高的 * self._queue 因为heappush的第一个参数给是个列表 * 后面元组的参数依次 优先级，插入的序号，和插入的内容 ~~~ 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] ~~~ * 实现效果 当优先级一样的时候，先返回，优先插入的 ~~~ class Item: def __init__(self,name): self.name = name def __repr__(self): return self.name q = PriorityQueue() q.push(Item('foo'),1) q.push(Item('fss'),2) q.push(Item('aaa'),1) print(q.pop()) print(q.pop()) print(q.pop()) 打印结果： fss foo aaa ~~~