Deques and heaps¶

~20 min · prerequisite: Sets, dictionaries, and anti-hash tests

What you will be able to do¶

Use a collections.deque as a queue, with fast operations at both ends.
Use the heapq module to get the smallest item repeatedly, and build a max-heap by negating values.
Use tuples as heap items so that a second value breaks ties in priority.

The idea¶

Lesson 1 said that removing the first item of a list shifts every other item, which is slow for long lists. A deque, short for "double-ended queue", is built for work at both ends. The method append adds at the right end, appendleft adds at the left, pop removes from the right, and popleft removes from the left. Each of these takes about the same time whatever the length. A deque is the usual choice for a queue, where items leave in the order they arrived, like a checkout line. Indexing in the middle of a deque is slower than in a list, so avoid dq[i] in long loops.

A heap answers "what is the smallest item now?" quickly, and it adds or removes items in about logarithmic time. Python's heapq module works on an ordinary list. The smallest item is always at index 0, but the rest of the list is only partly ordered, so heap[1] is not necessarily the second smallest. The function heapq.heappop returns the items in order. The function heapq.heapify turns an existing list into a heap in one pass. Use a heap when you need the smallest item again and again, and a single sort when you need the order once.

Python's heap is a min-heap, so the smallest value comes out first. For the largest value, store the negative of each number and negate it again when you read it. Tuples work well as heap items: a tuple such as (priority, name) is compared by its first part, and the second part breaks ties.

Worked example¶

from collections import deque
import heapq

line = deque(["ann", "ben"])
line.append("cy")
print(line.popleft())

jobs = []
heapq.heappush(jobs, (2, "write"))
heapq.heappush(jobs, (1, "test"))
heapq.heappush(jobs, (3, "deploy"))
print(heapq.heappop(jobs))
print(jobs[0])

The output is:

ann
(1, 'test')
(2, 'write')

Line by line, this is what Python does:

popleft removes the leftmost item, "ann", so the first person in line is served first.
Each heappush adds one tuple and moves it up until the heap rule holds. The number decides the order.
heappop removes and returns the smallest tuple, (1, 'test').
jobs[0] shows the smallest remaining item without removing it.

Try it¶

The block shows both ends of a deque and a max-heap built from negated values.

from collections import deque
import heapq

d = deque([1, 2, 3, 4])
d.rotate(1)
assert list(d) == [4, 1, 2, 3]
d.appendleft(0)
assert d.popleft() == 0
assert d.pop() == 3
assert list(d) == [4, 1, 2]

def largest_k(values, k):
    heap = [-v for v in values]
    heapq.heapify(heap)
    return [-heapq.heappop(heap) for _ in range(k)]

assert largest_k([5, 1, 9, 3], 2) == [9, 5]
assert largest_k([7, 7, 2], 3) == [7, 7, 2]

Common mistakes¶

Popping from an empty deque. Calling popleft() on an empty deque gives:
```
IndexError: pop from an empty deque
```
Test if q: before you remove an item.
Popping from an empty heap. Calling heapq.heappop([]) gives:
```
IndexError: index out of range
```
Pushing items that cannot be compared. Two tuples with the same first number and dictionaries as second parts give:
```
TypeError: '<' not supported between instances of 'dict' and 'dict'
```
Add a comparable second part, such as a name or an index.
Using list.pop(0) as a queue. This runs without an error, but each removal shifts the whole list, so large inputs run slowly. Use a deque.

Practice¶

Write the function named in each problem. The samples are checks.

Queue commands (easy). Write run_queue(commands). "push X" adds X at the back. "pop" outputs the front item, or "empty" if there is none. Sample: run_queue(["push 5", "push 7", "pop", "pop", "pop"]) returns ["5", "7", "empty"].
Smallest k (easy). Write k_smallest(values, k). Use a heap to return the k smallest values in ascending order. Sample: k_smallest([5, 1, 4, 2, 3], 2) returns [1, 2].
Window maximum (medium). Write window_max(nums, k). Return the largest value in each window of k consecutive items. Sample: window_max([1, 3, -1, -3, 5, 3, 6, 7], 3) returns [3, 3, 5, 5, 6, 7].
Task order (medium). Write schedule(tasks). Each task is (name, priority). Run the smallest priority number first, and break ties by name. Sample: schedule([("write", 2), ("test", 1), ("deploy", 3), ("lint", 1)]) returns ["lint", "test", "write", "deploy"].
Merge cost (stretch). Write merge_cost(lengths). Repeatedly join the two shortest pieces, paying the sum of their lengths, until one piece is left. Return the total cost, or 0 for at most one piece. Samples: merge_cost([4, 3, 2, 6]) returns 29, and merge_cost([1, 2, 3]) returns 9.

Solution

```python from collections import deque

def run_queue(commands): q = deque() out = [] for cmd in commands: if cmd.startswith("push "): q.append(cmd.split()[1]) elif q: out.append(q.popleft()) else: out.append("empty") return out

assert run_queue(["push 5", "push 7", "pop", "pop", "pop"]) == ["5", "7", "empty"] ```

```python import heapq

def k_smallest(values, k): heap = list(values) heapq.heapify(heap) return [heapq.heappop(heap) for _ in range(k)]

assert k_smallest([5, 1, 4, 2, 3], 2) == [1, 2] ```

```python from collections import deque

def window_max(nums, k): dq = deque() out = [] for i, x in enumerate(nums): while dq and nums[dq[-1]] <= x: dq.pop() dq.append(i) if dq[0] <= i - k: dq.popleft() if i >= k - 1: out.append(nums[dq[0]]) return out

assert window_max([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7] ```

The deque holds indexes whose values decrease from left to right, so its front is the current maximum.

```python import heapq

def schedule(tasks): heap = [(priority, name) for name, priority in tasks] heapq.heapify(heap) order = [] while heap: _, name = heapq.heappop(heap) order.append(name) return order

assert schedule([("write", 2), ("test", 1), ("deploy", 3), ("lint", 1)]) == ["lint", "test", "write", "deploy"] ```

```python import heapq

def merge_cost(lengths): heap = list(lengths) heapq.heapify(heap) total = 0 while len(heap) > 1: a = heapq.heappop(heap) b = heapq.heappop(heap) total += a + b heapq.heappush(heap, a + b) return total

assert merge_cost([4, 3, 2, 6]) == 29 assert merge_cost([1, 2, 3]) == 9 assert merge_cost([]) == 0 ```

Recap¶

A deque removes from either end quickly, so use it for queues and sliding windows instead of list.pop(0).
heapq keeps the smallest item at index 0. Negate numbers to get a max-heap.
Tuples such as (priority, name) order heap items by the first part and break ties with the second.