heapq : 堆隊(duì)列算法
Source code: Lib/heapq.py
介紹
這個(gè)模塊提供了堆隊(duì)列算法的實(shí)現(xiàn)，也稱為優(yōu)先隊(duì)列算法。
堆是一個(gè)特殊的二叉樹（本文檔中指的小頂堆，對(duì)應(yīng)還有大頂堆），它的每個(gè)父結(jié)點(diǎn)的值小于等于它的兩個(gè)孩子結(jié)點(diǎn)的值。
該文中的堆是基于數(shù)組來實(shí)現(xiàn)的靜態(tài)二叉樹咖气，對(duì)于數(shù)組中的每個(gè)元素
heapq.merge(\*iterables, key=None, reverse=False)
- 合并多個(gè)已排序(升序)的序列，返回一個(gè)可迭代對(duì)象
- 功能和
sorted(itertools.chain(*iterables))類似挖滤，但是它返回的是可迭代對(duì)象崩溪，它不會(huì)將所有的數(shù)據(jù)一次性放到內(nèi)存里面，并且以輸入的序列必須是
排序斩松、升序?yàn)榍疤?/li> - 有兩個(gè)可選參數(shù)：
- key參數(shù)制定了一個(gè)key函數(shù)伶唯，該函數(shù)用來指定輸入序列中用來排序的元素；
- reverse是一個(gè)bool值惧盹，若為true乳幸，則合并之后的元素倒排
eg：
a = [3, 1, 5, 7]
b = [2, 4, 6, 8]
c = merge(a, b)
for item in c:
print(item, sep=" ", end=" "
output:
1 2 3 4 5 6 7 8
基礎(chǔ)的例子
-
堆排序可以通過將所有的元素壓入堆中，然后每次從小頂堆中取出最小的元素（即二叉樹中的根節(jié)點(diǎn)）：
def heapsort(iterable): h = [] for value in iterable: heappush(h, value) return [heappop(h) for i in range(len(h))] heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) 上述的堆排序和內(nèi)置
sorted(iterable)函數(shù)很像钧椰，但是該堆排序不是穩(wěn)定的粹断，而sorted(iterable)是穩(wěn)定的排序；-
堆元素可以是元組嫡霞。這可以用于像任務(wù)優(yōu)先級(jí)中瓶埋，選取某個(gè)屬性來作為當(dāng)前的比較值：
h = [] heappush(h, (5, 'write code')) heappush(h, (7, 'release product')) heappush(h, (1, 'write spec')) heappush(h, (3, 'create tests')) heappop(h)
