看python cookbook時(shí)，關(guān)于heapq模塊中的heappush函數(shù)的一個(gè)疑問(wèn)

1.下面是書(shū)上的代碼，利用heapq模塊實(shí)現(xiàn)了一個(gè)優(yōu)先級(jí)隊(duì)列，每次pop函數(shù)優(yōu)先級(jí)高的被刪除并返回。

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.書(shū)上的使用方式

>>> 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')

我的問(wèn)題是，這個(gè)heappush函數(shù)的第二項(xiàng)參數(shù)是元組(-priority, self._index, item)，那它是根據(jù)什么來(lái)進(jìn)行堆排序的？（函數(shù)原型是heappush(heap, item) ）

如果是根據(jù)priority來(lái)進(jìn)行堆排序，我在heapqpush的源碼里似乎沒(méi)看到對(duì)item是元組時(shí)進(jìn)行處理的代碼？

回答

編輯回答

來(lái)守候

看源碼, heappush首先會(huì)把元素查到列表的尾部，然后調(diào)用下面的函數(shù)調(diào)整元素到合適的位置。

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: # 可以看到是直接用<運(yùn)算符進(jìn)行比較的
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

可以看到是直接用 < 運(yùn)算符比較元素，決定是否要移動(dòng)。
這里的第二個(gè)參數(shù)item被包裝成為了一個(gè)元組，然后利用<進(jìn)行判斷排序.
元組在比較大小的時(shí)候，首先比較第一個(gè)元素，如果能夠判斷那么就直接根據(jù)第一個(gè)元素進(jìn)行判斷，如果不能，就取下一個(gè)元素進(jìn)行判斷，依次類(lèi)推。直到比較出結(jié)果或者一方?jīng)]有元素了。