每日python——python中的堆排序模块heapq

2019-06-01 本文已影响0人咋家

python中的heapq模块提供了与堆排序有关的操作，关于堆的理解可以自行网上搜索相关知识，需要清楚的是，python中的堆是以最小堆为基础的，因此相应的pop操作，会弹出其中的最小元素，下面来看这个模块提供的一些方法。

首先，如何创建一个堆，一般会根据一个列表初始化创建一个堆，这需要函数heapify()来完成，对于空列表我们可以直接将其按照堆来对待进行相应操作，非空列表必须进行相应的创建操作。

>>> from heapq import *
>>> h =[5,4,3,2,1]
>>> heapify(h)
>>> h
[1, 2, 3, 5, 4]

heappush(heap, item)

将值item压入堆中

>>> heappush(h, 6)
>>> h
[1, 2, 3, 5, 4, 6]

heappop(heap)

返回堆中最小值

>>> heappop(h)
1
>>> h
[2, 4, 3, 5, 6]

heappushpop(heap, item)

先将值item压入堆中，再返回堆中最小值

>>> heappushpop(h, 7)
2
>>> h
[3, 4, 7, 5, 6]

heapreplace(heap, item)

与上面的相反先进行pop操作，然后进行push操作

>>> heapreplace(h, 8)
3
>>> h
[4, 5, 7, 8, 6]

merge(*iterable)

将多个有序列表合并成一个有序列表，类似与归并排序，切记得是有序列表

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

nlargest(n, iterable[, key]), nsmallest(n, iterable[,key])

获取列表中最大最小的n个值，key值可以指定特定的关键词排序

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, portfolio, key=lambda s: s['price'])