API Reference

pqdict class

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

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 (Mapping[Any, Any] | Iterable[Tuple[Any, Any]] | None) –

• key (Callable[[Any], Any] | None) –

• reverse (bool) –

• precedes (Callable[[Any, Any], bool]) –

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

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(*args, **kwargs)

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:

Tpqdict

classmethod maxpq(*args, **kwargs)

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:

Tpqdict

classmethod fromkeys(iterable, value, **kwargs)

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

Parameters:

• iterable (Iterable) –

• value (Any) –

• kwargs (Any) –

Return type:

Tpqdict

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]])

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: 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()

Return a shallow copy of a pqdict.

Parameters:

self (Tpqdict) –

Return type:

Tpqdict

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(default=<object object>)

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(default=<object object>)

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(default=<object object>)

Return the item with highest priority.

Raises Empty if pqdict is empty.

Parameters:

default (Any) –

Return type:

Tuple[Any, Any]

pop(*[, default])

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(default=<object object>)

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(default=<object object>)

Remove and return the item with highest priority.

Raises Empty if pqdict is empty.

Parameters:

default (Any) –

Return type:

Tuple[Any, Any]

additem(key, value)

Add a new item.

Raises KeyError if key is already in the pqdict.

Parameters:

• key (Any) –

• value (Any) –

Return type:

None

updateitem(key, new_val)

Update the priority value of an existing item.

Raises KeyError if key is not in the pqdict.

Parameters:

• key (Any) –

• new_val (Any) –

Return type:

None

pushpopitem(key, value)

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 (Any) –

• value (Any) –

Return type:

Tuple[Any, Any]

replace_key(key, new_key)

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 (Any) –

• new_key (Any) –

Return type:

None

swap_priority(key1, key2)

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

Raises KeyError if either key does not exist.

Parameters:

• key1 (Any) –

• key2 (Any) –

Return type:

None

heapify([key])

Repair a broken heap.

If the state of an item’s priority value changes you can re-sort the relevant item only by providing key.

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()

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

Return type:

Iterator[Any]

popvalues()

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

Return type:

Iterator[Any]

popitems()

Remove and return items in descending order of priority rank.

Return type:

Iterator[Tuple[Any, Any]]

Functions

pqdict.nsmallest(n, mapping, key=None)

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)

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])]