看python cookbook时，关于heapq模块中的heappush函数的一个疑问

Question

1.下面是书上的代码，利用heapq模块实现了一个优先级队列，每次pop函数优先级高的被删除并返回。

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]
    

2.书上的使用方式

>>> class Item:
...     def __init__(self, name):
...         self.name = name
...     def __repr__(self):
...         return 'Item({!r})'.format(self.name)
...
>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')

我的问题是，这个heappush函数的第二项参数是元组(-priority, self._index, item)，那它是根据什么来进行堆排序的？（ 函数原型是heappush(heap, item) ）

如果是根据priority来进行堆排序，我在heapqpush的源码里似乎没看到对item是元组时进行处理的代码？

Answer 1

看源码, heappush首先会把元素查到列表的尾部，然后调用下面的函数调整元素到合适的位置。

def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent: # 可以看到是直接用<运算符进行比较的
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

可以看到是直接用 < 运算符比较元素，决定是否要移动。
这里的第二个参数item被包装成为了一个元组，然后利用<进行判断排序.
元组在比较大小的时候，首先比较第一个元素，如果能够判断那么就直接根据第一个元素进行判断，如果不能，就取下一个元素进行判断，依次类推。直到比较出结果或者一方没有元素了。

1. (2,3) > (2,1) # True
2. (1,2,x) > (1,2,y) # 和 x > y 的值是相等的
3. (1，2) < (1,2,x) # True

然后按照这个规则作为优先级判断的规则，创建堆

然后你在代码里封装的这个元组，第一个元素是人工赋予的优先级，第二个是当前index，这样就可以保证根据元组的前两个元素就一定能得到确定的优先级了。