API reference¶

Everything below is importable from the top-level iheap package.

iheap.MAX_LEN is the largest number of handles a heap can issue (2³² − 1).

PQDict also has every method dict has. The standard ones it inherits unchanged (keys, values, items, __eq__, ...) behave exactly as they do for dict and are not repeated here.

PQDict ¶

PQDict(
    data: Mapping[K, V]
    | Iterable[tuple[K, V]]
    | None = None,
    *,
    key: PriorityFn[K, V] | None = None,
    reverse: bool = False,
)

Bases: MutableMapping[K, V], Generic[K, V]

A mapping of keys to values that also behaves as a priority queue.

The priority of an item is key(item_key, value) if a key function is given, otherwise the value itself. (Unlike pqdict, the function receives the item's key as well as its value.)

Priorities are numbers: anything float() accepts except str (int, float, Decimal, Fraction, numpy scalars). They are stored as float, so integers are exact up to 2**53. NaN is rejected. By default the item with the smallest priority is on top; pass reverse=True for a max-queue. Ties are popped in unspecified order.

Supports every dict operation (get, setdefault, |, |=, reversed, views, equality, pickling, ...). Like dict, iteration follows key insertion order; use popkeys, popitems etc. for priority order. Unlike dict, popitem removes the top-priority item rather than the last inserted one.

Only priorities are sent to the native heap; keys and values stay in Python.

Not safe for concurrent mutation: guard a queue that several threads modify with a lock (required on free-threaded Python).

Parameters:

Name	Type	Description	Default
`data`	`Mapping[K, V] \| Iterable[tuple[K, V]] \| None`	Initial items, as a mapping or an iterable of `(key, value)` pairs. Built in `O(n)` with a single native call.	`None`
`key`	`PriorityFn[K, V] \| None`	Function `(item_key, value) -> priority`. Defaults to using the value itself as the priority.	`None`
`reverse`	`bool`	If true, the largest priority is on top (max-queue).	`False`

Raises:

Type	Description
`TypeError`	A priority is not a number.
`ValueError`	A priority is NaN.

Examples:

>>> pq = PQDict({"a": 3, "b": 1}, reverse=True)
>>> pq["c"] = 5
>>> pq.top()
'c'
>>> list(pq.popitems())
[('c', 5), ('a', 3), ('b', 1)]
>>> by_len = PQDict({"pear": 1, "fig": 9}, key=lambda k, v: len(k) + v)
>>> by_len.top()
'pear'

keyfn `property` ¶

keyfn: PriorityFn[K, V] | None

The priority function, or None if values are priorities.

reverse `property` ¶

reverse: bool

True for a max-queue.

fromkeys `classmethod` ¶

fromkeys(
    iterable: Iterable[K],
    value: V = None,
    *,
    key: PriorityFn[K, V] | None = None,
    reverse: bool = False,
) -> PQDict[K, V]

Create a queue with keys from iterable, all set to value.

Parameters:

Name	Type	Description	Default
`iterable`	`Iterable[K]`	Keys to insert.	required
`value`	`V`	Value (and, without `key`, priority) shared by every key.	`None`
`key`	`PriorityFn[K, V] \| None`	Priority function, as in the constructor.	`None`
`reverse`	`bool`	Max-queue if true, as in the constructor.	`False`

get ¶

get(key: K, default: Any = None) -> Any

Return the value for key if present, else default.

setdefault ¶

setdefault(key: K, default: Any = None) -> Any

Return the value for key, inserting default first if absent.

update ¶

update(other: Any = (), /, **kwargs: V) -> None

Insert or update many items, like dict.update.

New keys are bulk-inserted (O(n) heapify when large) and existing keys bulk-updated, with one native call each. The operation is atomic: if any priority is invalid, nothing changes.

Parameters:

Name	Type	Description	Default
`other`	`Any`	A mapping or an iterable of `(key, value)` pairs.	`()`
`**kwargs`	`V`	Additional items.	`{}`

clear ¶

clear() -> None

Remove all items.

copy ¶

copy() -> PQDict[K, V]

Shallow copy; the native heap is cloned without re-heapifying.

pop ¶

pop(key: Any = _MISSING, default: Any = _MISSING) -> Any

Remove an item: the top one, or key with dict semantics.

Parameters:

Name	Type	Description	Default
`key`	`Any`	If given, remove this item and return its value. If omitted, remove the top item and return its key.	`_MISSING`
`default`	`Any`	Returned instead of raising when the item is missing (or the queue is empty).	`_MISSING`

Raises:

Type	Description
`KeyError`	`key` is missing, or the queue is empty, and no `default` was given.

popvalue ¶

popvalue(default: Any = _MISSING) -> Any

Remove the top item and return its value.

Raises:

Type	Description
`KeyError`	The queue is empty and no `default` was given.

popitem ¶

popitem() -> tuple[K, V]

Remove and return the top (key, value) pair.

Raises:

Type	Description
`KeyError`	The queue is empty.

top ¶

top(default: Any = _MISSING) -> Any

Return the key of the top item without removing it.

Raises:

Type	Description
`KeyError`	The queue is empty and no `default` was given.

topvalue ¶

topvalue(default: Any = _MISSING) -> Any

Return the value of the top item without removing it.

Raises:

Type	Description
`KeyError`	The queue is empty and no `default` was given.

topitem ¶

topitem() -> tuple[K, V]

Return the top (key, value) pair without removing it.

Raises:

Type	Description
`KeyError`	The queue is empty.

additem ¶

additem(key: K, value: V) -> None

Add a new item.

Raises:

Type	Description
`KeyError`	`key` is already present.

updateitem ¶

updateitem(key: K, new_val: V) -> None

Update the value (and priority) of an existing item.

Raises:

Type	Description
`KeyError`	`key` is missing.

pushpopitem ¶

pushpopitem(key: K, value: V) -> tuple[K, V]

Push an item, then pop and return the top one, in a single pass.

Faster than additem followed by popitem. If the new item would be on top, it is returned straight away and the queue is unchanged.

Raises:

Type	Description
`KeyError`	`key` is already present.

replace_key ¶

replace_key(key: K, new_key: K) -> None

Rename key to new_key, keeping its value.

Without a key function the priority is unchanged (O(1)); with one, it is recomputed as key(new_key, value).

Raises:

Type	Description
`KeyError`	`key` is missing or `new_key` is already present.

swap_priority ¶

swap_priority(key1: K, key2: K) -> None

Exchange the values of two items, and hence their priorities.

Without a key function this is O(1); with one, both priorities are recomputed from the new (key, value) pairs.

Raises:

Type	Description
`KeyError`	Either key is missing.

popkeys ¶

popkeys() -> Iterator[K]

Destructively iterate over keys in priority order.

popvalues ¶

popvalues() -> Iterator[V]

Destructively iterate over values in priority order.

popitems ¶

popitems() -> Iterator[tuple[K, V]]

Destructively iterate over (key, value) pairs in priority order.

heapify ¶

heapify(key: Any = _MISSING) -> None

Recompute priorities after values were mutated in place.

Only needed with a key function whose result depends on mutable state of the value.

Parameters:

Name	Type	Description	Default
`key`	`Any`	Re-prioritize only this item (`O(log n)`). If omitted, all items are re-prioritized (`O(n)`).	`_MISSING`

Raises:

Type	Description
`KeyError`	`key` is missing.

minpq ¶

minpq(*args: Any, **kwargs: Any) -> PQDict[Any, Any]

Create a min-priority queue from dict(*args, **kwargs).

Examples:

>>> minpq(a=3, b=1).top()
'b'

maxpq ¶

maxpq(*args: Any, **kwargs: Any) -> PQDict[Any, Any]

Create a max-priority queue from dict(*args, **kwargs).

Examples:

>>> maxpq(a=3, b=1).top()
'a'

nsmallest ¶

nsmallest(
    n: int,
    mapping: Mapping[K, V],
    key: PriorityFn[K, V] | None = None,
) -> list[K]

Return the keys of the n items with the smallest priorities.

Runs in O(N + n log N) in native code.

Parameters:

Name	Type	Description	Default
`n`	`int`	Number of keys to return.	required
`mapping`	`Mapping[K, V]`	Any mapping of keys to values.	required
`key`	`PriorityFn[K, V] \| None`	Function `(item_key, value) -> priority`. Defaults to the value.	`None`

Returns:

Type	Description
`list[K]`	Up to `n` keys, smallest priority first.

nlargest ¶

nlargest(
    n: int,
    mapping: Mapping[K, V],
    key: PriorityFn[K, V] | None = None,
) -> list[K]

Return the keys of the n items with the largest priorities.

Parameters:

Name	Type	Description	Default
`n`	`int`	Number of keys to return.	required
`mapping`	`Mapping[K, V]`	Any mapping of keys to values.	required
`key`	`PriorityFn[K, V] \| None`	Function `(item_key, value) -> priority`. Defaults to the value.	`None`

Returns:

Type	Description
`list[K]`	Up to `n` keys, largest priority first.

IndexedHeap ¶

IndexedHeap(
    *, reverse: object = False, capacity: SupportsIndex = 0
)

Native indexed priority queue of float priorities addressed by handles.

push returns an integer handle that stays valid until its entry is popped or removed, and lets you update or remove that entry in O(log n). Handles are small non-negative integers below handle_bound and are recycled, so you can keep per-entry data in a plain list indexed by handle. The heap itself holds no Python objects.

Priorities must be convertible to float and not NaN. Integers are exact up to 2**53. Handles may be any int-like (SupportsIndex); one that names no live entry, including negative or huge values, raises KeyError. Batch methods accept any iterable. Heaps pickle and copy exactly, including which handles will be reused next.

Thread safety: a heap may be shared between threads, including on free-threaded Python. Each call runs under an internal lock, so concurrent calls are serialized; sequences of calls are not atomic.

Parameters:

Name	Type	Description	Default
`reverse`	`object`	If true, the largest priority is on top (max-heap).	`False`
`capacity`	`SupportsIndex`	Number of entries to pre-allocate room for.	`0`

Raises:

Type	Description
`ValueError`	`capacity` is negative or above `MAX_LEN`.
`MemoryError`	`capacity` entries cannot be allocated.

Examples:

>>> heap = IndexedHeap()
>>> a, b = heap.push(3.0), heap.push(1.0)
>>> heap.peek() == (b, 1.0)
True
>>> heap.update(a, 0.5)
3.0
>>> heap.pop() == (a, 0.5)
True

reverse `property` ¶

reverse: bool

True for a max-heap.

handle_bound `property` ¶

handle_bound: int

Exclusive upper bound of every live handle (the handle high-water mark).

push ¶

push(priority: float) -> int

Insert an entry in O(log n).

Parameters:

Name	Type	Description	Default
`priority`	`float`	Priority of the new entry.	required

Returns:

Type	Description
`int`	The handle of the new entry.

Raises:

Type	Description
`ValueError`	`priority` is NaN.
`TypeError`	`priority` is not convertible to `float`.

push_many ¶

push_many(priorities: Iterable[float]) -> list[int]

Insert many entries at once.

Large batches are appended and re-heapified in O(n). Atomic: if any priority is invalid, nothing is inserted. On an empty heap after construction or clear, the returned handles are 0, 1, ..., len(priorities) - 1.

Parameters:

Name	Type	Description	Default
`priorities`	`Iterable[float]`	Priorities of the new entries.	required

Returns:

Type	Description
`list[int]`	Handles of the new entries, in input order.

Raises:

Type	Description
`ValueError`	A priority is NaN.

peek ¶

peek() -> tuple[int, float] | None

Return (handle, priority) of the top entry, or None if empty.

pop ¶

pop() -> tuple[int, float]

Remove and return the top entry in O(log n).

Returns:

Type	Description
`int`	`(handle, priority)` of the removed entry. The handle becomes
`float`	invalid and may be reused by later pushes.

Raises:

Type	Description
`IndexError`	The heap is empty.

push_pop ¶

push_pop(priority: float) -> tuple[int, float] | None

Fused push-then-pop in a single pass (like heapq.heappushpop).

Parameters:

Name	Type	Description	Default
`priority`	`float`	Priority of the new entry.	required

Returns:

Type	Description
`tuple[int, float] \| None`	`None` if the new entry would be popped right away (the heap is
`tuple[int, float] \| None`	empty or its top does not strictly precede `priority`); the heap
`tuple[int, float] \| None`	is then unchanged. Otherwise the top entry is popped, **its handle
`tuple[int, float] \| None`	is reassigned to the new entry**, and `(handle, popped_priority)`
`tuple[int, float] \| None`	is returned.

Raises:

Type	Description
`ValueError`	`priority` is NaN.

pop_many ¶

pop_many(n: SupportsIndex) -> list[tuple[int, float]]

Pop up to n entries (none if n <= 0).

Returns:

Type	Description
`list[tuple[int, float]]`	`(handle, priority)` pairs in priority order.

priority ¶

priority(handle: SupportsIndex) -> float

Return the priority of handle.

Raises:

Type	Description
`KeyError`	`handle` is not live.

update ¶

update(handle: SupportsIndex, priority: float) -> float

Change the priority of handle in O(log n).

Returns:

Type	Description
`float`	The previous priority.

Raises:

Type	Description
`KeyError`	`handle` is not live.
`ValueError`	`priority` is NaN.

update_many ¶

update_many(
    handles: Iterable[SupportsIndex],
    priorities: Iterable[float],
) -> None

Change many priorities at once.

Re-heapifies in O(n) when that is cheaper than individual updates. Atomic: on error nothing changes. If a handle appears more than once, the last priority wins.

Raises:

Type	Description
`KeyError`	A handle is not live.
`ValueError`	The lists differ in length, or a priority is NaN.

remove ¶

remove(handle: SupportsIndex) -> float

Remove handle in O(log n).

Returns:

Type	Description
`float`	The priority of the removed entry.

Raises:

Type	Description
`KeyError`	`handle` is not live.

clear ¶

clear() -> None

Remove every entry. Handle numbering restarts at 0.

items ¶

items() -> list[tuple[int, float]]

Return live (handle, priority) pairs in handle order (not priority order).

copy ¶

copy() -> IndexedHeap

Return an independent copy, handles included.

API reference¶

PQDict ¶

keyfn property ¶

reverse property ¶

fromkeys classmethod ¶

get ¶

setdefault ¶

update ¶

clear ¶

copy ¶

pop ¶

popvalue ¶

popitem ¶

top ¶

topvalue ¶

topitem ¶

additem ¶

updateitem ¶

pushpopitem ¶

replace_key ¶

swap_priority ¶

popkeys ¶

popvalues ¶

popitems ¶

heapify ¶

minpq ¶

maxpq ¶

nsmallest ¶

nlargest ¶

IndexedHeap ¶

reverse property ¶

handle_bound property ¶

push ¶

push_many ¶

peek ¶

pop ¶

push_pop ¶

pop_many ¶

priority ¶

update ¶

update_many ¶

remove ¶

clear ¶

items ¶

copy ¶

keyfn `property` ¶

reverse `property` ¶

fromkeys `classmethod` ¶

reverse `property` ¶

handle_bound `property` ¶