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

heapq的全寫是heapqueue，是堆隊列的意思。這里的堆和隊列都是數(shù)據(jù)結(jié)構(gòu)，在后序的文章當(dāng)中我們會詳細(xì)介紹，今天只介紹heapq的用法，如果不了解heap和queue原理的同學(xué)可以忽略，我們并不會深入太多，會在之后的文章里詳細(xì)闡述。

在介紹用法之前，我們需要先知道優(yōu)先隊列的定義。隊列大家應(yīng)該都不陌生，也是非?；A(chǔ)簡單的數(shù)據(jù)結(jié)構(gòu)。我們可以想象成隊列里的所有元素排成一排，新的元素只能從隊尾加入隊列，元素要出隊列只能通過隊首，不能中途從隊列當(dāng)中退出。而優(yōu)先隊列呢，是給隊列當(dāng)中的元素每一個都設(shè)置了優(yōu)先級，使得隊伍當(dāng)中的元素會自動按照優(yōu)先級排序，優(yōu)先級高的排在前面。

也就是說Python當(dāng)中的heapq就是一個維護(hù)優(yōu)先隊列的library，我們通過調(diào)用它可以輕松實現(xiàn)優(yōu)先隊列的功能。

最大或最小的K個元素

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

這個問題在實際當(dāng)中非常常見，隨便就可以舉出例子來。比如用戶輸入了搜索詞，我們根據(jù)用戶的搜索詞找到了大量的內(nèi)容。我們想要根據(jù)算法篩選出用戶最有可能點擊的文本來，機(jī)器學(xué)習(xí)的模型可以給每一個文本一個預(yù)測的分?jǐn)?shù)。之后，我們就需要選出分?jǐn)?shù)最大的K個結(jié)果。這種類似的場景還有很多，利用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接受兩個參數(shù)，第一個參數(shù)是K，也就是返回的元素的數(shù)量，第二個參數(shù)是傳入的數(shù)組，heapq返回的正是傳入的數(shù)組當(dāng)中的前K大或者是前K小。

這里有一個問題，如果我們數(shù)組當(dāng)中的元素是一個對象呢?應(yīng)該怎么辦?

其實也很簡單，有了解過Python自定義關(guān)鍵詞排序的同學(xué)應(yīng)該知道，和排序一樣，我們可以通過匿名函數(shù)實現(xiàn)。

匿名函數(shù)

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

初學(xué)者可能會納悶，函數(shù)沒有名字應(yīng)該怎么調(diào)用呢?

會有這個疑惑很正常，這是因為習(xí)慣了面向過程的編程，對面向?qū)ο罄斫獠粔蛏钊雽?dǎo)致的。在許多高級語言當(dāng)中，一切皆對象，一個類，一個函數(shù)，一個int都是對象。既然函數(shù)也是對象，那么函數(shù)自然也可以用來傳遞，不僅可以用來傳遞，還可以用來返回。這是函數(shù)式編程的概念了，我們這里不多做深入。

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

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

defoperate(x,func):

returnfunc(x)

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

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

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)

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

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

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

square=lambdax:x**2

print(square(3))

print(operate(3,square))

自定義排序

回到之前的內(nèi)容，如果我們想要heapq排序的是一個對象。那么heapq并不知道應(yīng)該依據(jù)對象當(dāng)中的哪個參數(shù)來作為排序的衡量標(biāo)準(zhǔn)，所以這個時候，需要我們自己定義一個獲取關(guān)鍵字的函數(shù)，傳遞給heapq，這樣才可以完成排序。

比如說，我們現(xiàn)在有一批電腦，我們希望heapq能夠根據(jù)電腦的價格排序：

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'])

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

優(yōu)先隊列

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

當(dāng)然我們也可以從零開始，直接通過調(diào)用heapq的push和pop來維護(hù)這個堆。接下來，我們就通過heapq來自己動手實現(xiàn)一個優(yōu)先隊列，代碼非常的簡單，我想大家應(yīng)該可以瞬間學(xué)會。

首先是實現(xiàn)優(yōu)先隊列的部分：

importheapq

classPriorityQueue:

def__init__(self):

self._queue=[]

self._index=0

defpush(self,item,priority):

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

#由于heap內(nèi)部默認(rèn)有小到大排，所以對priority取負(fù)數(shù)

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

到這里，關(guān)于heapq的應(yīng)用方面就算是介紹完了，但是還沒有真正的結(jié)束。

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

defnlargest(n,iterable,key=None):

"""Findthenlargestelementsinadataset.

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

"""

以上內(nèi)容為大家介紹了Python中heapq與優(yōu)先隊列，希望對大家有所幫助，如果想要了解更多Python相關(guān)知識，請關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。