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 (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>)[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
]) – IfTrue
, larger priority keys give items higher priority. Default isFalse
.precedes (callable, optional [default:
operator.lt
]) – Function that determines precedence of a pair of priority keys. The default comparator isoperator.lt
, meaning smaller priority keys give items higher priority. The callable must have the formprecedes(prio1, prio2) -> bool
and returnTrue
ifprio1
has higher priority thanprio2
. Overridesreverse
.
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 theprecedes
keyword argument. Alternatively, use the explicitpqdict.minpq()
orpqdict.maxpq()
class methods.
- classmethod minpq(*args, **kwargs)[source]
Create a pqdict with min-priority semantics: smallest value is highest.
pqdict.minpq()
-> new empty pqdict with min-priority semanticspqdict.minpq(mapping)
-> new minpq initialized from a mappingpqdict.minpq(iterable)
-> new minpq initialized from an iterable of pairspqdict.minpq(**kwargs)
-> new minpq initialized with name=value pairs
- Parameters:
args (Any) –
kwargs (Any) –
- Return type:
Tpqdict
- classmethod maxpq(*args, **kwargs)[source]
Create a pqdict with max-priority semantics: largest value is highest.
pqdict.maxpq()
-> new empty pqdict with max-priority semanticspqdict.maxpq(mapping)
-> new maxpq initialized from a mappingpqdict.maxpq(iterable)
-> new maxpq initialized from an iterable of pairspqdict.maxpq(**kwargs)
-> new maxpq initialized with name=value pairs
- Parameters:
args (Any) –
kwargs (Any) –
- Return type:
Tpqdict
- classmethod fromkeys(iterable, value, **kwargs)[source]
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]])[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, returndefault
if provided, otherwise raise aKeyError
.
- 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()[source]
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()
, andpopitems()
.- 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>)[source]
Return the key of the item with highest priority.
If
default
is provided and pqdict is empty, then returndefault
, otherwise raiseEmpty
.- Parameters:
default (Any) –
- Return type:
Any
- topvalue(default=<object object>)[source]
Return the value of the item with highest priority.
If
default
is provided and pqdict is empty, then returndefault
, otherwise raiseEmpty
.- Parameters:
default (Any) –
- Return type:
Any
- topitem(default=<object object>)[source]
Return the item with highest priority.
Raises
Empty
if pqdict is empty.- Parameters:
default (Any) –
- Return type:
Tuple[Any, 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 raiseEmpty
.
- popvalue(default=<object object>)[source]
Remove and return the value of the item with highest priority.
If
default
is provided and pqdict is empty, then returndefault
, otherwise raiseEmpty
.- Parameters:
default (Any) –
- Return type:
Any
- popitem(default=<object object>)[source]
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)[source]
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)[source]
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)[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 (Any) –
value (Any) –
- Return type:
Tuple[Any, Any]
- 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 (Any) –
new_key (Any) –
- 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 (Any) –
key2 (Any) –
- Return type:
None
- heapify([key])[source]
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()[source]
Remove items, returning keys in descending order of priority rank.
- Return type:
Iterator[Any]
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])]