深入了解Python之heapq內建模組介紹

高洛峰
發布: 2017-03-15 14:19:27
原創
2654 人瀏覽過

heapq 是 python 的內建模組,原始碼位於 Lib/heapq.py ,該模組提供了基於堆疊的優先排序演算法。

堆的邏輯結構就是完全二元樹,而二元樹中父節點的值小於等於該節點的所有子節點的值。這種實作可以使用heap[k] <= heap[2k+1] 並且heap[k] <= heap[2k+2] (其中k 為索引,從0 開始計數)的形式體現,對堆來說,最小元素即為根元素heap[0]。

可以透過list 對heap 進行初始化,或透過api# 中的heapify 將已知的list 轉換為heap 物件

heapq 提供的函數方法

#heapq.heappush(heap, item)

heapq.heappop(heap):傳回root 節點,即heap 中最小的元素

heapq.heappushpop(heap, item):向heap 中加入item 元素,並傳回heap 中最小元素

heapq.heapify(x)

heapq.nlargest(n, iterable, key=None):傳回可列舉物件中的n 個最大值,並傳回一個結果集list,key 為對該結果集的操作

heapq.nsmallest(n, iterable, key=None):同上相反

##demo

# 1. 透過heapq api 對list 進行排序

def heapsort(iterable):
    h = []

    for i in iterable:
        heapq.heappush(h, i)

    return [heapq.heappop(h) for i in range(len(h))]


s = [3, 5, 1, 2, 4, 6, 0, 1]
print(heapsort(s))
登入後複製

#輸出如下

#

 [0, 1, 1, 2, 3, 4, 5, 6]
登入後複製

2. 透過key,找出物件清單中price 最小的一項

portfolio = [
    {&#39;name&#39;: &#39;IBM&#39;, &#39;shares&#39;: 100, &#39;price&#39;: 91.1},
    {&#39;name&#39;: &#39;AAPL&#39;, &#39;shares&#39;: 50, &#39;price&#39;: 543.22},
    {&#39;name&#39;: &#39;FB&#39;, &#39;shares&#39;: 200, &#39;price&#39;: 21.09},
    {&#39;name&#39;: &#39;HPQ&#39;, &#39;shares&#39;: 35, &#39;price&#39;: 31.75},
    {&#39;name&#39;: &#39;YHOO&#39;, &#39;shares&#39;: 45, &#39;price&#39;: 16.35},
    {&#39;name&#39;: &#39;ACME&#39;, &#39;shares&#39;: 75, &#39;price&#39;: 115.65}
]
cheap = heapq.nsmallest(1, portfolio, key=lambda s: s[&#39;price&#39;])
print(cheap)
登入後複製

輸出如下

[{&#39;shares&#39;: 45, &#39;price&#39;: 16.35, &#39;name&#39;: &#39;YHOO&#39;}]
登入後複製

# extend

上文講到heapq 是最小堆的實現,那麼我們根據heapq 的源碼分析一下在python 中如何透過api 實現將list 轉換為最小堆(父節點的關鍵字比左右子節點都小)

可分為以下幾步操作:

1. 從最後一個有子節點的元素開始,將這個父節點元素和其子節點看做一個單元

2. 在單元中,將兩個子節點中較小的元素與父節點調換位置(不需要判斷父節點和這個最小子節點的大小關係),透過這一步驟操作即可將這個單元變更為最小堆單元

3. 透過

while 循環可以將較小的元素向上推

def heapilize_list(x):
    n = len(x)
    # 获取存在子节点的节点 index 列表,并对每个节点单元进行最小堆处理
    for i in reversed(range(n // 2)):
        raiseup_node(x, i)

def put_down_node(heap, startpos, pos):
    current_item = heap[pos]
    # 判断单元中最小子节点与父节点的大小
    while pos > startpos:
        parent_pos = (pos - 1) >> 1
        parent_item = heap[parent_pos]

        if current_item < parent_item:
            heap[pos] = parent_item
            pos = parent_pos
            continue
        break

    heap[pos] = current_item

def raiseup_node(heap, pos):
    heap_len = len(heap)
    start_pos = pos
    current_item = heap[pos]
    left_child_pos = pos * 2 + 1

    while left_child_pos < heap_len:
        right_child_pos = left_child_pos + 1
        # 将这个单元中的最小子节点元素与父节点元素进行位置调换
        if right_child_pos < heap_len and not heap[left_child_pos] < heap[right_child_pos]:
            left_child_pos = right_child_pos
        heap[pos] = heap[left_child_pos]
        pos = left_child_pos
        left_child_pos = pos * 2 + 1
    heap[pos] = current_item
    put_down_node(heap, start_pos, pos)


p = [4, 6, 2, 10, 1]
heapilize_list(p)
print(p)
登入後複製

輸出如下

#

[1, 6, 2, 10, 4]
登入後複製

 ###

以上是深入了解Python之heapq內建模組介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!