# 8.4. `heapq` — 堆队列算法¶

2.3 新版功能.

`heapq.``heappush`(heap, item)

item 的值加入 heap 中，保持堆的不变性。

`heapq.``heappop`(heap)

`heapq.``heappushpop`(heap, item)

item 放入堆中，然后弹出并返回 heap 的最小元素。该组合操作比先调用 `heappush()` 再调用 `heappop()` 运行起来更有效率。

2.6 新版功能.

`heapq.``heapify`(x)

`heapq.``heapreplace`(heap, item)

`heapq.``merge`(*iterables)

2.6 新版功能.

`heapq.``nlargest`(n, iterable[, key])

Return a list with the n largest elements from the dataset defined by iterable. key, if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: `key=str.lower` Equivalent to: ```sorted(iterable, key=key, reverse=True)[:n]```

2.4 新版功能.

`heapq.``nsmallest`(n, iterable[, key])

Return a list with the n smallest elements from the dataset defined by iterable. key, if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: `key=str.lower` Equivalent to: `sorted(iterable, key=key)[:n]`

2.4 新版功能.

## 8.4.1. 基本示例¶

```>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```

```>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')
```

## 8.4.2. 优先队列实现说明¶

• 排序稳定性：你该如何令相同优先级的两个任务按它们最初被加入时的顺序返回？

• In the future with Python 3, tuple comparison breaks for (priority, task) pairs if the priorities are equal and the tasks do not have a default comparison order.

• 如果任务优先级发生改变，你该如何将其移至堆中的新位置？

• 或者如果一个挂起的任务需要被删除，你该如何找到它并将其移出队列？

Removing the entry or changing its priority is more difficult because it would break the heap structure invariants. So, a possible solution is to mark the existing entry as removed and add a new entry with the revised priority:

```pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
counter = itertools.count()     # unique sequence count

count = next(counter)
heappush(pq, entry)

entry[-1] = REMOVED

'Remove and return the lowest priority task. Raise KeyError if empty.'
while pq:
raise KeyError('pop from an empty priority queue')
```

## 8.4.3. 理论¶

```                               0

1                                 2

3               4                5               6

7       8       9       10      11      12      13      14

15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30
```

1