【Python进阶】1.4补充 Python heapq模块

欢迎关注Julia语言微信公众账号 julia_language

原文链接：http://suo.im/5nqIQs

微信公众号：Julia语言
每周一三五更新Julia语言；
每周二四六更新Python进阶;

这个模块(build-in)实现了一个堆的数据结构，完美的解决了Top-K问题，以后解决Top-K问题的时候，直接把这个模块拿来用就可以了。注意，默认的heap是一个小顶堆！

heapq模块提供了如下几个函数：

• heapq.heappush(heap, item) 把item添加到heap中（heap是一个列表）
• heapq.heappop(heap) 把堆顶元素弹出，返回的就是堆顶
• heapq.heappushpop(heap, item) 先把item加入到堆中，然后再pop，比heappush()再heappop()要快得多
• heapq.heapreplace(heap, item) 先pop，然后再把item加入到堆中，比heappop()再heappush()要快得多
• heapq.heapify(x) 将列表x进行堆调整，默认的是小顶堆
• heapq.merge(*iterables) 将多个列表合并，并进行堆调整，返回的是合并后的列表的迭代器
• heapq.nlargest(n, iterable, key=None) 返回最大的n个元素（Top-K问题）
• heapq.nsmallest(n, iterable, key=None) 返回最小的n个元素（Top-K问题）

import heapq
import random
 
# Top-K
mylist = list(random.sample(range(100), 10))
k = 3
largest = heapq.nlargest(k, mylist)
smallest = heapq.nsmallest(k, mylist)
print('original list is', mylist)
print('largest-'+str(k), '  is ', largest)
print('smallest-'+str(k), ' is ', smallest)
 
# heapify
print('original list is', mylist)
heapq.heapify(mylist)
print('heapify  list is', mylist)
 
# heappush & heappop
heapq.heappush(mylist, 105)
print('pushed heap is', mylist)
heapq.heappop(mylist)
print('popped heap is', mylist)
 
# heappushpop & heapreplace
heapq.heappushpop(mylist, 130)    # heappush -> heappop
print('heappushpop', mylist)
heapq.heapreplace(mylist, 18)    # heappop -> heappush
print('heapreplace', mylist)

输出的结果为：

original list is [8, 83, 26, 98, 12, 66, 10, 16, 56, 22]
largest-3   is  [98, 83, 66]
smallest-3  is  [8, 10, 12]
original list is [8, 83, 26, 98, 12, 66, 10, 16, 56, 22]
heapify  list is [8, 12, 10, 16, 22, 66, 26, 98, 56, 83]
pushed heap is [8, 12, 10, 16, 22, 66, 26, 98, 56, 83, 105]
popped heap is [10, 12, 26, 16, 22, 66, 105, 98, 56, 83]
heappushpop [12, 16, 26, 56, 22, 66, 105, 98, 130, 83]
heapreplace [16, 18, 26, 56, 22, 66, 105, 98, 130, 83]

欢迎关注微信公众账号Julia语言.jpg

点击阅读原文可查看历史文章