Python cookbook（数据结构与算法）找到最大或最小的N个元素实现

>>> import heapq
>>> nums=[1,8,2,23,7,-4,18,42,37,2]
>>> print(heapq.nlargest(3,nums))
[42,23]
>>> print(heapq.nsmallest(3,nums))
[-4,1,2]
>>>

# example.py
#
# Example of using heapq to find the N smallest or largest items
import heapq
portfolio = [
 {'name': 'IBM','shares': 100,'price': 91.1},{'name': 'AAPL','shares': 50,'price': 543.22},{'name': 'FB','shares': 200,'price': 21.09},{'name': 'HPQ','shares': 35,'price': 31.75},{'name': 'YHOO','shares': 45,'price': 16.35},{'name': 'ACME','shares': 75,'price': 115.65}
]
cheap = heapq.nsmallest(3,portfolio,key=lambda s: s['price'])
expensive = heapq.nlargest(3,key=lambda s: s['price'])
print(cheap)
print(expensive)

Python 3.4.0 (v3.4.0:04f714765c13,Mar 16 2014,19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright","credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
[{'name': 'YHOO','price': 16.35,'shares': 45},'price': 21.09,'shares': 200},'price': 31.75,'shares': 35}]
[{'name': 'AAPL','price': 543.22,'shares': 50},'price': 115.65,'shares': 75},{'name': 'IBM','price': 91.1,'shares': 100}]
>>>

>>> import heapq
>>> nums=[1,2]
>>> heap=list(nums)
>>> heap
[1,2]
>>> heapq.heapify(heap) #heapify()参数必须是list，此函数将list变成堆，实时操作。从而能够在任何情况下使用堆的函数。
>>> heap
[-4,8]
>>> heapq.heappop(heap)#如下是为了找到第3小的元素
-4
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
2
>>>

>>> h=[]   #定义一个list
>>> from heapq import * #引入heapq模块
>>> h
[]
>>> heappush(h,5)  #向堆中依次增加数值
>>> heappush(h,2)
>>> heappush(h,3)
>>> heappush(h,9)
>>> h    #h的值
[2,5,3,9]
>>> heappop(h)   #从h中删除最小的，并返回该值
2
>>> h
[3,9]
>>> h.append(1)   #注意，如果不是压入堆中，而是通过append追加一个数值
>>> h    #堆的函数并不能操作这个增加的数值，或者说它堆对来讲是不存在的
[3,9,1]
>>> heappop(h)   #从h中能够找到的最小值是3,而不是1
3
>>> heappush(h,2)  #这时，不仅将2压入到堆内，而且1也进入了堆。
>>> h
[1,5]
>>> heappop(h)   #操作对象已经包含了1
1

>>> h
[1,5]
>>> heappop(h)
1
>>> heappushpop(h,4)  #增加4同时删除最小值2并返回该最小值，与下列操作等同：
2    #heappush(h,4),heappop(h)
>>> h
[4,9]

>>> a=[3,6,1]
>>> heapify(a)   #将a变成堆之后，可以对其操作
>>> heappop(a)
1
>>> b=[4,5]   #b不是堆，如果对其进行操作，显示结果如下
>>> heappop(b)   #按照顺序，删除第一个数值并返回,不会从中挑选出最小的
4
>>> heapify(b)   #变成堆之后，再操作
>>> heappop(b)
2

>>> a=[]
>>> heapreplace(a,3)  #如果list空，则报错
Traceback (most recent call last):
File "<stdin>",line 1,in <module>
IndexError: index out of range
>>> heappush(a,3)
>>> a
[3]
>>> heapreplace(a,2)  #先执行删除（heappop(a)->3),再执行加入（heappush(a,2))
3
>>> a
[2]
>>> heappush(a,5)
>>> heappush(a,9)
>>> heappush(a,4)
>>> a
[2,4,5]
>>> heapreplace(a,6)  #先从堆a中找出最小值并返回，然后加入6
2
>>> a
[4,6]
>>> heapreplace(a,1)  #1是后来加入的，在1加入之前，a中的最小值是4
4
>>> a
[1,6]

>>> a=[2,6]
>>> b=[1,5]
>>> c=merge(a,b)
>>> list(c)
[1,6]