Python高性能計算之堆

  很多Python的初學者可能對Python中的堆不太了解，堆是一種用于快速查找并提取集合中最大值或最小值的資料結構，它的典型用途就是按照優先級處理一系列的任務。

  我們在前面講清單和雙端隊列時，講到過清單中的查找操作的時間複雜度是O(N)，但如果清單是有序的，我們就可以使用子產品

bisect

實作時間複雜度為O(log(N))的查找操作。但雖然查找的時間縮短了，但如果要再進行插值，時間複雜度依然是O(N)。而堆是一種效率更高的資料結構，其元素插入操作和最大值提取操作的時間複雜度都是O(log(N))。

  Python中，使用

heapq

庫來進行堆的一系列操作。

heapq

中常用的函數：

Fucntion	Description
heapfiy()	将清單轉化為堆結構
heappop()	從堆中彈出最小的元素
heappush(heap, x)	将x壓入堆中
heapreplace(heap, x)	彈出最小元素，并将x壓入堆中
nlargest(n, iter)	傳回iter中n個最大元素
nsmallest(n, iter)	傳回iter中n個最小元素

下面我們來看如何使用堆來完成高效的操作。

• 建立堆結構

  有兩種方式可以建立堆結構，一種是建立一個空的list，然後一個數一個數的往裡壓；一種是把list轉成堆結構

import heapq
lst = [5, 2, 4, 1, 2, 8, 5, 4]
heapq.heapify(lst)   # 轉化為堆結構 

heap = []
for i in range(10):
    heappush(heap, i)
           

• 彈出值

heapq.heappop(lst) # 取出最小值 
>>> 1
heapq.heappop(lst) #
>>> 2
           

• 将元素壓入堆中

heapq.heappush(lst, 3) # 插值3
heapq.heappop(lst)
>>> 2
heapq.heappop(lst)
>>> 3
           

• 傳回值但不彈出

heapq.nsamllest(3, lst) # 傳回3個最小值
heapq.nlargest(3, lst) # 傳回3個最大值
           

系列文章：

1. Python高性能計算之清單

2. Python高性能計算之字典

3. Python高性能計算之堆

4. Python高性能計算之字典樹

5. Python常用操作的複雜度

微信公衆号：Quant_Times