API Reference

pqdict class

class pqdict.pqdict(data=None, key=None, reverse=False, precedes=<built-in function lt>)[source]

A mutable dict/priority queue that maps hashable keys to priority values.

As a priority queue, items can be added and the top-priority item can be viewed or dequeued. In addition, arbitrary items may be retrieved, removed, and have their priorities updated by key.

Parameters:

data (DictInputs[KT, VT] | None)
key (PriorityKeyFn | None)
reverse (bool)
precedes (PrecedesFn)

__init__(data=None, key=None, reverse=False, precedes=<built-in function lt>)[source]

Create a new priority queue dictionary.

Parameters:

data (mapping or iterable, optional) – Input data, e.g. a dictionary or a sequence of items.
key (callable, optional) – Optional priority key function to transform values into priority keys for comparison. By default, the values are used directly as priority keys and are not transformed.
reverse (bool, optional [default: False]) – If True, larger priority keys give items higher priority. Default is False.
precedes (callable, optional [default: operator.lt]) – Function that determines precedence of a pair of priority keys. The default comparator is operator.lt, meaning smaller priority keys give items higher priority. The callable must have the form precedes(prio1, prio2) -> bool and return True if prio1 has higher priority than prio2. Overrides reverse.

Notes

The default behavior is that of a min-priority queue, i.e. the item with the smallest value is given highest priority. This behavior can be reversed by specifying reverse=True or by providing a custom precedence function via the precedes keyword argument. Alternatively, use the explicit pqdict.minpq() or pqdict.maxpq() class methods.

classmethod minpq() → pqdict[Any, Any][source]

classmethod minpq(**kwargs: _V) → pqdict[str, _V]

classmethod minpq(mapping: Mapping[_K, _V], /) → pqdict[_K, _V]

classmethod minpq(iterable: Iterable[tuple[_K, _V]], /) → pqdict[_K, _V]

Create a pqdict with min-priority semantics: smallest value is highest.

pqdict.minpq() -> new empty pqdict with min-priority semantics
pqdict.minpq(mapping) -> new minpq initialized from a mapping
pqdict.minpq(iterable) -> new minpq initialized from an iterable of pairs
pqdict.minpq(**kwargs) -> new minpq initialized with name=value pairs

Parameters:

args (Any)
kwargs (Any)

Return type:

pqdict[Any, Any]

classmethod maxpq() → pqdict[Any, Any][source]

classmethod maxpq(**kwargs: _V) → pqdict[str, _V]

classmethod maxpq(mapping: Mapping[_K, _V], /) → pqdict[_K, _V]

classmethod maxpq(iterable: Iterable[tuple[_K, _V]], /) → pqdict[_K, _V]

Create a pqdict with max-priority semantics: largest value is highest.

pqdict.maxpq() -> new empty pqdict with max-priority semantics
pqdict.maxpq(mapping) -> new maxpq initialized from a mapping
pqdict.maxpq(iterable) -> new maxpq initialized from an iterable of pairs
pqdict.maxpq(**kwargs) -> new maxpq initialized with name=value pairs

Parameters:

args (Any)
kwargs (Any)

Return type:

pqdict[Any, Any]

classmethod fromkeys(iterable: Iterable[_K], value: _V, /) → pqdict[_K, _V][source]

classmethod fromkeys(iterable: Iterable[_K], value: _V, **kwargs: Any) → pqdict[_K, _V]

Return a new pqdict mapping keys from an iterable to the same value.

Parameters:

iterable (Any)
value (Any)
kwargs (Any)

Return type:

pqdict[Any, Any]

Properties

keyfn: Priority key function.

precedes: Priority key precedence function.

Dictionary API

These do as expected. See dict for more details.

len(pq)

pq[key]()

pq[key] = value

del pq[key]

key in pq

get(key[, default]): D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.

pop([key[, default]])[source]

Hybrid pop method.

With key, perform a dictionary pop:

If key is in the pqdict, remove the item and return its value.
If key is not in the pqdict, return default if provided, otherwise raise a KeyError.

clear() → None. Remove all items from D.

update([other]): D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. If E present and has a .keys() method, does: for k in E.keys(): D[k] = E[k] If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v In either case, this is followed by: for k, v in F.items(): D[k] = v

setdefault(key[, default]): D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D

copy()[source]

Return a shallow copy of a pqdict.

Return type:: Self

Iterators and Views

Warning

For the sequences returned by the following methods, the iteration order is arbitrary.

See further below for sorted iterators popkeys(), popvalues(), and popitems().

iter(pq)

keys() → a set-like object providing a view on D's keys

values() → an object providing a view on D's values

items() → a set-like object providing a view on D's items

Priority Queue API

top() → KT[source]

top(default: _T) → KT | _T

Return the key of the item with highest priority.

If default is provided and pqdict is empty, then return default, otherwise raise Empty.

Parameters:: default (Any)
Return type:: Any

topvalue() → VT[source]

topvalue(default: _T) → VT | _T

Return the value of the item with highest priority.

If default is provided and pqdict is empty, then return default, otherwise raise Empty.

Parameters:: default (Any)
Return type:: Any

topitem() → tuple[KT, VT][source]

topitem(default: _T) → tuple[KT, VT] | _T

Return the item with highest priority.

Raises Empty if pqdict is empty.

Parameters:: default (Any)
Return type:: Any

pop(*[, default])[source]

Hybrid pop method.

Without key, perform a priority queue pop:

Remove the top item and return its key.
If the pqdict is empty, return default if provided, otherwise raise Empty.

popvalue() → VT[source]

popvalue(default: _T) → VT | _T

Remove and return the value of the item with highest priority.

If default is provided and pqdict is empty, then return default, otherwise raise Empty.

Parameters:: default (Any)
Return type:: Any

popitem() → tuple[KT, VT][source]

popitem(default: _T) → tuple[KT, VT] | _T

Remove and return the item with highest priority.

Raises Empty if pqdict is empty.

Parameters:: default (Any)
Return type:: Any

additem(key, value)[source]

Add a new item.

Raises KeyError if key is already in the pqdict.

Parameters:

key (KT)
value (VT)

Return type:

None

updateitem(key, new_val)[source]

Update the priority value of an existing item.

Raises KeyError if key is not in the pqdict.

Parameters:

key (KT)
new_val (VT)

Return type:

None

pushpopitem(key, value)[source]

Insert a new item and return the top-priority item.

Equivalent to inserting a new item followed by removing the top priority item, but faster. Raises KeyError if the new key is already in the pqdict.

Parameters:

key (KT)
value (VT)

Return type:

tuple[KT, VT]

replace_key(key, new_key)[source]

Replace the key of an existing heap node in place.

Raises KeyError if the key to replace does not exist or if the new key is already in the pqdict.

Parameters:

key (KT)
new_key (KT)

Return type:

None

swap_priority(key1, key2)[source]

Fast way to swap the priority level of two items in the pqdict.

Raises KeyError if either key does not exist.

Parameters:

key1 (KT)
key2 (KT)

Return type:

None

heapify() → None[source]

heapify(key: KT, /) → None

Repair a broken heap.

If a change in a single, mutable value caused the break, you can provide key to repair the heap by relocating that item.

Parameters:: key (Any)
Return type:: None

Sorted Iterators

Note

Iteration is in descending order of priority.

Warning

Sorted iterators are destructive: they are generators that pop items out of the heap, which amounts to performing a heapsort.

popkeys()[source]

Remove items, returning keys in descending order of priority rank.

Return type:: Iterator[KT]

popvalues()[source]

Remove items, returning values in descending order of priority rank.

Return type:: Iterator[VT]

popitems()[source]

Remove and return items in descending order of priority rank.

Return type:: Iterator[tuple[KT, VT]]

Functions

pqdict.nsmallest(n, mapping, key=None)[source]

Return the n keys associated with the smallest values in a mapping.

Takes a mapping and returns the n keys associated with the smallest values in ascending order. If the mapping has fewer than n items, all its keys are returned.

Parameters:

n (int) – The number of keys associated with the smallest values in ascending order
mapping (Mapping) – A dict-like object
key (callable, optional) – Optional priority key function to transform values into priority keys for sorting. By default, the values are not transformed.

Return type:

list of up to n keys from the mapping associated with the smallest values

Notes

This function is equivalent to:

>>> [item[0] for item in heapq.nsmallest(n, mapping.items(), lambda x: x[1])]

pqdict.nlargest(n, mapping, key=None)[source]

Return the n keys associated with the largest values in a mapping.

Takes a mapping and returns the n keys associated with the largest values in descending order. If the mapping has fewer than n items, all its keys are returned.

Parameters:

n (int) – The number of keys associated with the largest values in descending order
mapping (Mapping) – A dict-like object
key (callable, optional) – Optional priority key function to transform values into priority keys for sorting. By default, the values are not transformed.

Return type:

list of up to n keys from the mapping associated with the largest values

Notes

This function is equivalent to:

>>> [item[0] for item in heapq.nlargest(n, mapping.items(), lambda x: x[1])]