【学习笔记】heapq

Python内置的heapq模块

import heapq

1. heapq.heappush(heap,item) # 将 item 压入到 heap 里面

items = [1,2,9,7,3] heapq.heappush(items,10) items [1, 2, 9, 7, 3, 10]

2. heapq.heappop(heap) # 将 heap 里面的最小值 pop 出 heap ，heap 为空的时候报 indexError 的错误

items [1, 2, 9, 7, 3, 10] heapq.heappop(items) 1 items [2, 3, 9, 7, 10]

3. heapq.heappushpop(heap,item) # pop出 heap 中最小的元素，推入到 item

items [2, 3, 9, 7, 10] heapq.heappushpop(items,11) 2 items [3, 7, 9, 11, 10]

4. heapq.heapify(x) # 将 list X 转化为 heap

nums = [1,10,9,8] nums [1, 10, 9, 8] heap = list(nums) heapq.heapify(heap) heap [1, 8, 9, 10]

5. heapq.heapreplace(heap,item)：pop出最小值，推入item，heap的size不变

heap [1, 8, 9, 10] heapq.heapreplace(heap,100) 1 heap [8, 10, 9, 100]

*6. heapq.merge(iterable)：将多个可迭代合并，并且排好序，返回一个iterator

heap [8, 10, 9, 100] heap1 = [10,67,56,80,79] h = heapq.merge(heap,heap1) list(h) [8, 10, 9, 10, 67, 56, 80, 79, 100]

P.S: 需要 说明的是这里所谓的排序不是完全排序，只是两个list对应位置比较，将小的值先push，然后大的值再与另外一个list的下一个值比较

7. heapq.nlargest(n,iterable,key)：返回item中大到小顺序的前N个元素，key默认为空，可以用来指定规则如：function等来处理特定的排序

8. heapq.nsmallest(n,iterable,key)：返回item中小到大顺序的前N个元素，key默认为空，可以用来指定规则如：function等来处理特定的排序

To create a heap, use a list initialized to[], or you can transform a populated list into a heap via functionheapify().

创建heap可以通过创建list，和使用heapify方法来实现