heapq取列表最大或最小值元素

在一個(gè)集合中獲取最大或者最小的n個(gè)元素,這時(shí)候就可以使用heapq模塊中有nlargest和nsmallest函數(shù)可以達(dá)到需求

heapq介紹:

    heapq模塊實(shí)現(xiàn)了python中的堆排序，并提供了有關(guān)方法。讓用Python實(shí)現(xiàn)排序算法有了簡(jiǎn)單快捷的方式。

>>> a=[1,2,5,9,72,-4]
>>> import heapq

#獲取列表中最小的兩個(gè)元素

>>> heapq.nsmallest(2,a)
[-4, 1]

#獲取列表中最大的兩個(gè)元素

>>> heapq.nlargest(2,a)
[72, 9]

其他函數(shù)說(shuō)明:

heappush()

heapq.heappush(heap, item):將item壓入到堆數(shù)組heap中。如果不進(jìn)行此步操作，后面的heappop()失效

heappop()

heapq.heappop(heap):從堆數(shù)組heap中取出最小的值，并返回。

>>> h=[]                    #定義一個(gè)list
>>> from heapq import *     #引入heapq模塊
>>> h
[]
>>> heappush(h,5)               #向堆中依次增加數(shù)值
>>> heappush(h,2)
>>> heappush(h,3)
>>> heappush(h,9)
>>> h                           #h的值
[2, 5, 3, 9]
>>> heappop(h)                  #從h中刪除最小的，并返回該值
2
>>> h
[3, 5, 9]
>>> h.append(1)                 #注意，如果不是壓入堆中，而是通過(guò)append追加一個(gè)數(shù)值
>>> h                           #堆的函數(shù)并不能操作這個(gè)增加的數(shù)值，或者說(shuō)它堆對(duì)來(lái)講是不存在的
[3, 5, 9, 1]
>>> heappop(h)                  #從h中能夠找到的最小值是3,而不是1
3
>>> heappush(h,2)               #這時(shí)，不僅將2壓入到堆內(nèi)，而且1也進(jìn)入了堆。
>>> h
[1, 2, 9, 5]
>>> heappop(h)                  #操作對(duì)象已經(jīng)包含了1
1

heapq.heappushpop(heap, item)

是上述heappush和heappop的合體，同時(shí)完成兩者的功能.注意：相當(dāng)于先操作了heappush(heap,item),然后操作heappop(heap)

>>> h
[1, 2, 9, 5]
>>> heappop(h)
1
>>> heappushpop(h,4)            #增加4同時(shí)刪除最小值2并返回該最小值，與下列操作等同：
2                               #heappush(h,4),heappop(h)
>>> h
[4, 5, 9]
heapq.heapify(x)
x必須是list，此函數(shù)將list變成堆，實(shí)時(shí)操作。從而能夠在任何情況下使用堆的函數(shù)。
>>> a=[3,6,1]
>>> heapify(a)                  #將a變成堆之后，可以對(duì)其操作
>>> heappop(a)
1
>>> b=[4,2,5]                   #b不是堆，如果對(duì)其進(jìn)行操作，顯示結(jié)果如下
>>> heappop(b)                  #按照順序，刪除第一個(gè)數(shù)值并返回,不會(huì)從中挑選出最小的
4
>>> heapify(b)                  #變成堆之后，再操作
>>> heappop(b)
2

heapq.heapreplace(heap, item)

是heappop(heap)和heappush(heap,item)的聯(lián)合操作。注意，與heappushpop(heap,item)的區(qū)別在于，順序不同，這里是先進(jìn)行刪除，后壓入堆

>>> a=[]
>>> heapreplace(a,3)            #如果list空，則報(bào)錯(cuò)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: index out of range
>>> heappush(a,3)
>>> a
[3]
>>> heapreplace(a,2)            #先執(zhí)行刪除（heappop(a)->3),再執(zhí)行加入（heappush(a,2))
3
>>> a
[2]
>>> heappush(a,5)  
>>> heappush(a,9)
>>> heappush(a,4)
>>> a
[2, 4, 9, 5]
>>> heapreplace(a,6)            #先從堆a(bǔ)中找出最小值并返回，然后加入6
2
>>> a
[4, 5, 9, 6]
>>> heapreplace(a,1)            #1是后來(lái)加入的，在1加入之前，a中的最小值是4
4
>>> a
[1, 5, 9, 6]
heapq.merge(*iterables)

舉例：

>>> a=[2,4,6]         
>>> b=[1,3,5]
>>> c=merge(a,b)
>>> list(c)
[1, 2, 3, 4, 5, 6]
在歸并排序中詳細(xì)演示了本函數(shù)的使用方法。
heapq.nlargest(n, iterable[, key]),heapq.nsmallest(n, iterable[, key])
獲取列表中最大、最小的幾個(gè)值。
>>> a   
[2, 4, 6]
>>> nlargest(2,a)
[6, 4]

注:其他函數(shù)出自https://github.com/qiwsir/algorithm/blob/master/heapq.md