cid c2ecfa5dc568f03c11df698b0743608d3bf6921537dd7c8e86ce7b244794833a · original · open access · via pydoc
Title: heapq — Heap queue algorithm — Python 3.13.18 documentation
Authors:
Venue: pydoc
Year: 2001
Canonical: pydoc:heapq@3.13
URL: https://docs.python.org/3.13/library/heapq.html
Collector: pydoc
OA: true
ABSTRACT
heapq — Heap queue algorithm — Python 3.13.18 documentation Navigation index modules | next | previous | Python » 3.13.18 Documentation » The Python standard library » Data Types » heapq — Heap queue algorithm | Theme Auto Light Dark | heapq — Heap queue algorithm¶ Source code: Lib/heapq.py This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. Heaps are binary trees for which every parent node has a value less than or equal to any of its children. We refer to this condition as the heap invariant. This implementation uses arrays for which heap[k] 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] This is similar to sorted(iterable), but unlike sorted(), this implementation is not stable. Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked: 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') Priority Queue Implementation Notes¶ A priority queue is common use for a heap, and it presents several implementation challenges: Sort stability: how do you get two tasks with equal priorities to be returned in the order they were originally added? Tuple comparison breaks for (priority, task) pairs if the priorities are equal and the tasks do not have a default comparison order. If the priority of a task changes, how do you move it to a new position in the heap? Or if a pending task needs to be deleted, how do you find it and remove it from the queue? A solution to the first two challenges is to store entries as 3-element list including the priority, an entry count, and the task. The entry count serves as a tie-breaker so that two tasks with the same priority are returned in the order they were added. And since no two entry counts are the same, the tuple comparison will never attempt to directly compare two tasks. Another solution to the problem of non-comparable tasks is to create a wrapper class that ignores the task item and only compares the priority field: from dataclasses import dataclass, field from typing import Any @dataclass(order=True) class PrioritizedItem: priority: int item: Any=field(compare=False) The remaining challenges revolve around finding a pending task and making changes to its priority or removing it entirely. Finding a task can be done with a dictionary pointing to an entry in the queue. 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 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 REMOVED = '' # placeholder for a removed task counter = itertools.count() # unique sequence count def add_task(task, priority=0): 'Add a new task or update the priority of an existing task' if task in entry_finder: remove_task(task) count = next(counter) entry = [priority, count, task] entry_finder[task] = entry heappush(pq, entry) def remove_task(task): 'Mark an existing task as REMOVED. Raise KeyError if not found.' entry = entry_finder.pop(task) entry[-1] = REMOVED def pop_task(): 'Remove and return the lowest priority task. Raise KeyError if empty.' while pq: priority, count, task = heappop(pq) if task is not REMOVED: del entry_finder[task] return task raise KeyError('pop from an empty priority queue') Theory¶ Heaps are arrays for which a[k]