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

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

# example.py## Example of using heapq to find the N smallest or largest itemsimport heapqportfolio = [ {'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, portfolio, 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 win32Type "copyright", "credits" or "license()" for more information.>>> ================================ RESTART ================================>>>[{'name': 'YHOO', 'price': 16.35, 'shares': 45}, {'name': 'FB', 'price': 21.09, 'shares': 200}, {'name': 'HPQ', 'price': 31.75, 'shares': 35}][{'name': 'AAPL', 'price': 543.22, 'shares': 50}, {'name': 'ACME', 'price': 115.65, 'shares': 75}, {'name': 'IBM', 'price': 91.1, 'shares': 100}]>>>

>>> import heapq>>> nums=[1,8,2,23,7,-4,18,23,42,37,2]>>> heap=list(nums)>>> heap[1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]>>> heapq.heapify(heap) #heapify()参数必须是list，此函数将list变成堆，实时操作。从而能够在任何情况下使用堆的函数。>>> heap[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 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, 5, 9]>>> h.append(1)   #注意，如果不是压入堆中，而是通过append追加一个数值>>> h    #堆的函数并不能操作这个增加的数值，或者说它堆对来讲是不存在的[3, 5, 9, 1]>>> heappop(h)   #从h中能够找到的最小值是3,而不是13>>> heappush(h,2)  #这时，不仅将2压入到堆内，而且1也进入了堆。>>> h[1, 2, 9, 5]>>> heappop(h)   #操作对象已经包含了11

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

>>> a=[3,6,1]>>> heapify(a)   #将a变成堆之后，可以对其操作>>> heappop(a)1>>> b=[4,2,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, 9, 5]>>> heapreplace(a,6)  #先从堆a中找出最小值并返回，然后加入62>>> a[4, 5, 9, 6]>>> heapreplace(a,1)  #1是后来加入的，在1加入之前，a中的最小值是44>>> a[1, 5, 9, 6]

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