Python中的堆队列

Python部落组织翻译,禁止转载,欢迎转发

堆队列一般用于表示有优先级的队列. 在Python中, 标准库'heapq'是用来处理堆队列的. 在Python中这个数据结构的特性是, 每次pop它都pop出最小的元素.

堆队列的一些操作:

1. heapify(iterable): 这个函数用于将一个可迭代对象转化为一个堆队列. 同时, 以堆队列的顺序排列.

2. heappush(heap, ele): 这个函数用于将一个元素加入到堆队列中, 顺序会被自动调整, 堆队列的结构会被自动维护.

3. theappop(heap): 这个函数从堆队列中取出最小的元素, 堆队列的结构会被自动维护.

heap01.png

输出:

heap02.png

4. heappushpop(heap, ele): 这个函数结合了heappush和heappop两个操作, 提高了效率, 堆队列的结构在操作完成后维护.

5. heapreplace(heap, ele): 这个函数也用一句玩完成pop和push两个操作, 但是和上面函数不同的是, 元素是先pop再push, 所以比压入值更大的值可能被返回.

heap03.png

输出

heap04.png

6. nlargest(k, iterable, key = func): 这个函数从iterable中返回最大的k个符合key条件的元素.

7. nsmallest(k, iterable, key = func): 这个函数从iterable中返回最小的k个符合key条件的元素.

heap05.png

输出

heap06.png


英文原文:http://www.geeksforgeeks.org/heap-queue-or-heapq-in-python/

译者:诗书塞外

 

2月15日11:00到13:00网站停机维护,13:00前恢复