优先队列

队列：队列里的所有元素排成一排，新的元素只能从队尾加入队列，元素要出队列只能通过队首，不能中途从队列当中退出。
优先队列：给队列当中的元素每一个都设置了优先级，使得队伍当中的元素会自动按照优先级排序，优先级高的排在前面。

使用heapq可以轻松实现优先队列的功能。

最大或最小的k个元素

通过heapq里的nlargest和nsmallest可以做到

import heapq
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接受两个参数，第一个参数是K，也就是返回的元素的数量，第二个参数是传入的数组，heapq返回的正是传入的数组当中的前K大或者是前K小。

对象数组中的排序

如果传入的是对象数组而不是数值数组，可以通过匿名函数实现排序

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, laptops, key=lambda s: s['price'])
expensive = heapq.nlargest(3, laptops, key=lambda s: s['price'])

优先队列实现

heapq除了可以返回最大最小的K个数之外，还实现了优先队列的接口。我们可以直接调用heapq.heapify方法，输入一个数组，返回的结果是根据这个数组生成的堆。
可以使用heapq的push和pop方法实现优先队列

import heapq
class PriorityQueue:
  def __init__(self):
    self._queue = []
    self._index =0
  def push(self, item, priority):
    # 传入两个参数，一个是存放元素的数组，另一个是要存储的元素，这里是一个元组。
    # 由于heap内部默认由小到大排，所以对priority取负数
    heapq.heappush(self._queue, (-priority, self._index, item))
    self._index += 1
  def pop(self):
    return heapq.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