今天的文章來介紹Python當中一個蠻有用的庫——heapq。

heapq的全寫是heapqueue，是堆隊列的意思。這里的堆和隊列都是數據結構，在后序的文章當中我們會詳細介紹，今天只介紹heapq的用法，如果不了解heap和queue原理的同學可以忽略，我們并不會深入太多，會在之后的文章里詳細闡述。

在介紹用法之前，我們需要先知道優先隊列的定義。隊列大家應該都不陌生，也是非常基礎簡單的數據結構。我們可以想象成隊列里的所有元素排成一排，新的元素只能從隊尾加入隊列，元素要出隊列只能通過隊首，不能中途從隊列當中退出。而優先隊列呢，是給隊列當中的元素每一個都設置了優先級，使得隊伍當中的元素會自動按照優先級排序，優先級高的排在前面。

也就是說Python當中的heapq就是一個維護優先隊列的library，我們通過調用它可以輕松實現優先隊列的功能。

最大或最小的K個元素

我們來看一個實際的問題，假設我們當下有N個雜亂無章的元素，但是我們只關心其中最大的K個或者是最小的K個元素。我們想從整個數組當中將這部分抽取出來，應該怎么辦呢?

這個問題在實際當中非常常見，隨便就可以舉出例子來。比如用戶輸入了搜索詞，我們根據用戶的搜索詞找到了大量的內容。我們想要根據算法篩選出用戶最有可能點擊的文本來，機器學習的模型可以給每一個文本一個預測的分數。之后，我們就需要選出分數最大的K個結果。這種類似的場景還有很多，利用heapq庫里的nlargest和nsmallest接口可以非常方便地做到這點。

我們一起來看一個例子：

importheapq

nums=[14,20,5,28,1,21,16,22,17,28]

heapq.nlargest(3,nums)

#[28,28,22]

heapq.nsmallest(3,nums)

#[1,5,14]

heapq的nlargest和nsmallest接受兩個參數，第一個參數是K，也就是返回的元素的數量，第二個參數是傳入的數組，heapq返回的正是傳入的數組當中的前K大或者是前K小。

這里有一個問題，如果我們數組當中的元素是一個對象呢?應該怎么辦?

其實也很簡單，有了解過Python自定義關鍵詞排序的同學應該知道，和排序一樣，我們可以通過匿名函數實現。

匿名函數

我們都知道，在Python當中通過def可以定義一個函數。通過def定義的函數都有函數名，所以稱為有名函數。除了有名函數之外，Python還支持匿名函數。顧名思義，就是沒有函數名的函數。也就是說它其他方面都和普通函數一樣，只不過沒有名字而已。

初學者可能會納悶，函數沒有名字應該怎么調用呢?

會有這個疑惑很正常，這是因為習慣了面向過程的編程，對面向對象理解不夠深入導致的。在許多高級語言當中，一切皆對象，一個類，一個函數，一個int都是對象。既然函數也是對象，那么函數自然也可以用來傳遞，不僅可以用來傳遞，還可以用來返回。這是函數式編程的概念了，我們這里不多做深入。

當然，普通函數也一樣可以傳遞，起到的效果一樣。只不過在編程當中，有些函數我們只會使用一次，沒必要再單獨定義一個函數，使用匿名函數會非常方便。

舉個例子，比方說我有一個這樣的函數：

defoperate(x,func):

returnfunc(x)

這個operate函數它接受兩個參數，第一個參數是變量x，第二個參數是一個函數。它會在函數內部調用func，返回func調用的結果。我現在要做這樣一件事情，我希望根據x這個整數對4取余的余數來判斷應該用什么樣的func。如果對4的余數為0，我希望求一次方，如果余數是2，我希望求平方，以此類推。如果按照正常的方法，我們需要實現4個方法，然后依次傳遞。

這當然是可以的，不過非常麻煩，如果使用匿名函數，就可以大大簡化代碼量：

defget_result(x):

ifx%4==0:

returnoperate(x,lambdax:x)

elifx%4==1:

returnoperate(x,lambdax:x**2)

elifx%4==2:

returnoperate(x,lambdax:x**3)

else:

returnoperate(x,lambdax:x**4)

在上面的代碼當中，我們通過lambda關鍵字定義了匿名函數，避免了定義四種函數用來傳遞的情況。當然，這個問題還有更簡單的寫法，可以只用一個函數解決。

我們來看lambda定義匿名函數的語法，首先是lambda關鍵字，表示我們當下定義的是一個匿名函數。之后跟的是這個匿名函數的參數，我們只用到一個變量x，所以只需要寫一個x。如果我們需要用到多個參數，通過逗號分隔，當然也可以不用參數。寫完參數之后，我們用冒號分開，冒號后面寫的是返回的結果。

我們也可以把匿名函數賦值給一個變量，之后我們就可以和調用普通函數一樣來調用了：

square=lambdax:x**2

print(square(3))

print(operate(3,square))

自定義排序

回到之前的內容，如果我們想要heapq排序的是一個對象。那么heapq并不知道應該依據對象當中的哪個參數來作為排序的衡量標準，所以這個時候，需要我們自己定義一個獲取關鍵字的函數，傳遞給heapq，這樣才可以完成排序。

比如說，我們現在有一批電腦，我們希望heapq能夠根據電腦的價格排序：

laptops=[

{'name':'ThinkPad','amount':100,'price':91.1},

{'name':'Mac','amount':50,'price':543.22},

{'name':'Surface','amount':200,'price':21.09},

{'name':'Alienware','amount':35,'price':31.75},

{'name':'Lenovo','amount':45,'price':16.35},

{'name':'Huawei','amount':75,'price':115.65}

]

cheap=heapq.nsmallest(3,portfolio,key=lambdas:s['price'])

expensive=heapq.nlargest(3,portfolio,key=lambdas:s['price'])

在調用nlargest和nsmallest的時候，我們額外傳遞了一個參數key，我們傳入的是一個匿名函數，它返回的結果是這個對象的price，也就是說我們希望heapq根據對象的price來進行排序。

優先隊列

heapq除了可以返回最大最小的K個數之外，還實現了優先隊列的接口。我們可以直接調用heapq.heapify方法，輸入一個數組，返回的結果是根據這個數組生成的堆(等價于優先隊列)。

當然我們也可以從零開始，直接通過調用heapq的push和pop來維護這個堆。接下來，我們就通過heapq來自己動手實現一個優先隊列，代碼非常的簡單，我想大家應該可以瞬間學會。

首先是實現優先隊列的部分：

importheapq

classPriorityQueue:

def__init__(self):

self._queue=[]

self._index=0

defpush(self,item,priority):

#傳入兩個參數，一個是存放元素的數組，另一個是要存儲的元素，這里是一個元組。

#由于heap內部默認有小到大排，所以對priority取負數

heapq.heappush(self._queue,(-priority,self._index,item))

self._index+=1

defpop(self):

returnheapq.heappop(self._queue)[-1]

其次我們來實際看一下運用的情況：

q=PriorityQueue()

q.push('lenovo',1)

q.push('Mac',5)

q.push('ThinkPad',2)

q.push('Surface',3)

q.pop()

#Mac

q.pop()

#Surface

到這里，關于heapq的應用方面就算是介紹完了，但是還沒有真正的結束。

我們需要分析一下heapq當中操作的復雜度，關于堆的部分我們暫時跳過，我們先來看nlargest和nsmallest。我在github當中找到了這個庫的源碼，在方法的注釋上，作者寫下了這個方法的復雜度，和排序之后取前K個開銷五五開：

defnlargest(n,iterable,key=None):

"""Findthenlargestelementsinadataset.

Equivalentto:sorted(iterable,key=key,reverse=True)[:n]

"""

以上內容為大家介紹了Python中heapq與優先隊列，希望對大家有所幫助，如果想要了解更多Python相關知識，請關注IT培訓機構:千鋒教育。