priority_search_tree

class priority_search_tree.PrioritySearchSet(key_func: Callable[[_V], _KEY], priority_func: Callable[[_V], _PRIORITY], iterable: Iterable[_V] | None = None)[source]

Mutable Set that maintains priority search tree properties.

PrioritySearchSet can be used to store any type of objects. 2 functions should be passed to PrioritySearchSet constructor:

  • key_func to extract key for the object

  • priority_func to extract priority for the object

extracted key, priority values will be used in underlying PrioritySearchTree

Example:

@dataclass
class Point:
    x: int
    y: int

# create new set with Point.x as key and Point.y as priority
pss = PrioritySearchSet(key_func=lambda p: p.x,
                        priority_func=lambda p: p.y,
                        iterable=[Point(1, 1), Point(2, 2)])
# add new item to set
pss.add(Point(3, 3))
# 3-sided query
result = pss.query(Point(1, 1), Point(3, 1), Point(2, 2))
# result = [Point(x=3, y=3), Point(x=2, y=2)]
Parameters:

  • key_func (Callable) – Specifies a function of one argument that is used to extract a comparison key (for example, key_func=lambda p: p.x).

  • priority_func (Callable) – Specifies a function of one argument that is used to extract a priority value (for example, priority_func=lambda p: p.y).

  • iterable (Iterable) – Initial values to build priority search set. The default value is None.

Raises:

KeyError – in case if iterable contains values with not unique key

Complexity:

O(N*log(N)) where N is number of items to be added to new PSS

__contains__(value: _V) → bool[source]

Membership test operator

Parameters:

value – Value to test for membership

Returns:

True if value is in self, False otherwise.

Return type:

bool

Complexity:

O(log(N)) where N is number of items in PSS

Note

this function is using key_func(value) to compare the items

__init__(key_func: Callable[[_V], _KEY], priority_func: Callable[[_V], _PRIORITY], iterable: Iterable[_V] | None = None) → None[source]
__iter__() → Iterator[source]

Create an iterator that iterates values in sorted by key order

Returns:

in order iterator

Return type:

Iterator

__len__() → int[source]

Implements the built-in function len()

Returns:

Number of items in PSS.

Return type:

int

Complexity:

O(1)

add(value: _V) → None[source]

Add new item to priority search Set.

Parameters:

value – Value to insert into PSS

Raises:

KeyError – in case if value already exists in PSS

Complexity:

O(log(N)) where N is number of items in PSS

Note

this function is using key_func(value) to compare the items

clear() → None[source]

Removes all items from priority search set.

Complexity:

O(1)

discard(value) → None[source]

Remove value from PSS if it exists.

Parameters:

value – Value to remove from PSS

Complexity:

O(log(N)) where N is number of items in PSS

Note

this function is using key_func(value) to compare the items

get_with_max_priority() → _KEY[source]

Return the item with the largest priority from the PSS.

Returns:

item with the largest priority

Raises:

KeyError – If the PSS is empty

Complexity:

Amortized O(1)

pop() → _V[source]

Remove and return the item with the largest priority from the PSS.

Returns:

item with the largest priority

Raises:

KeyError – If the PSS is empty

Complexity:

O(log(N)) where N is number of items in PSS

query(left: _V, right: _V, bottom: _V) → list[source]

Performs 3 sided query on PSS.

This function returns list of items that meet the following criteria:

  1. items have key grater or equal to key of left argument

  2. items have key smaller or equal to key of right argument

  3. items have priority grater or equal to priority of bottom argument

Parameters:

  • left – Left bound for query (key is used to compare).

  • right – Right bound for query (key is used to compare).

  • bottom – Bottom bound for query (priority is used to compare).

Returns:

list of items that satisfy criteria, or empty list if no items found

Return type:

List

Complexity:

O(log(N)+K) where N is number of items in PSS and K is number of reported items

remove(value: _V) → None[source]

Remove value from PSS.

Parameters:

value – Value to remove from PSS

Raises:

KeyError – in case if value not exists in PSS

Complexity:

O(log(N)) where N is number of items in PSS

Note

this function is using key_func(value) to compare the items

sorted_query(left: _V, right: _V, bottom: _V, items_limit: int = 0) → list[source]

Performs sorted 3 sided query on PSS.

This function returns list of items that meet the following criteria:

  1. items have key grater or equal to key of left argument

  2. items have key smaller or equal to key of right argument

  3. items have priority grater or equal to priority of bottom argument

Parameters:

  • left – Left bound for query (key is used).

  • right – Right bound for query (key is used).

  • bottom – Bottom bound for query (priority is used).

  • items_limit (int) – Number of items to return. Default value is 0 - no limit.

Returns:

list of items that satisfy criteria and sorted by priority (in case of limit, items with largest priority will be returned), or empty list if no items found.

Return type:

List

Complexity:

O(log(N)+K*log(K)) where N is number of items in PSS and K is number of returned items

class priority_search_tree.PrioritySearchTree(iterable: Iterable[Tuple[_KEY, _PRIORITY]] | None = None)[source]

Class that represents Priority search tree.

PrioritySearchTree is a mutable mapping that stores keys and corresponding priorities.

  • Keys are stored in balanced binary search tree (red/black tree) that allow to effectively perform next operations:

    • in order traversal

    • find min/max keys

    • find next/previous keys

  • Priorities and keys form max priority queue, that allow to effectively perform next operations:

    • find element with max priority

    • remove element with max priority

    • update priority for a given key

  • It is capable to perform 3 sided queries

Example:

# create new tree
pst = PrioritySearchTree([(1,1),(2,2)])
# add key 3 to the tree with priority 5
pst[3] = 5
# perform 3 sided query
result = pst.query(0,4,2)
Parameters:

iterable (Iterable) – Initial values to build priority search tree. Each item in the iterable must itself be an iterable with exactly two objects. The first object of each item becomes a key in the new pst, and the second object the corresponding priority. The default value is None.

Raises:

KeyError – in case if iterable contains values with not unique key

Complexity:

O(N*log(N)) where N is number of items to be added to new PST

__delitem__(key: _KEY) → None[source]

Remove key from PST.

Parameters:

key – key to remove

Raises:

KeyError – in case if key not exists in PST

Complexity:

O(log(N)) where N is number of items in PST

__getitem__(key: _KEY) → _PRIORITY[source]

Returns priority of given key in PST.

Parameters:

key – key to find

Returns:

priority value if the given key

Raises:

KeyError – in case if key not exists in PST

Complexity:

O(log(N)) where N is number of items in PST

__init__(iterable: Iterable[Tuple[_KEY, _PRIORITY]] | None = None) → None[source]
__iter__() → Iterator[source]

Create an iterator that iterates keys in sorted order

Returns:

in order iterator

Return type:

Iterator

__len__() → int[source]

Implements the built-in function len()

Returns:

Number of items in PST.

Return type:

int

Complexity:

O(1)

__setitem__(key: _KEY, priority: _PRIORITY) → None[source]

implements assignment operation.

Parameters:

  • key – key to add/update

  • priority – new priority

Complexity:

O(log(N)) where N is number of items in PST

clear() → None[source]

Removes all items from PST.

Complexity:

O(1)

get_with_max_priority() → _KEY[source]

Returns the key with the largest priority in PST.

Returns:

key with the largest priority

Raises:

KeyError – If the PST is empty

Complexity:

O(1)

popitem() → Tuple[_KEY, _PRIORITY][source]

Remove and return (key, priority) pair from the PST. Pair with max priority will be removed.

Returns:

key and priority pair

Return type:

Tuple

Raises:

KeyError – If the PST is empty

Complexity:

O(log(N)) where N is number of items in PST

query(key_left: _KEY, key_right: _KEY, priority_bottom: _PRIORITY) → list[source]

Performs 3 sided query on PST.

This function returns list of items that meet the following criteria:

  1. items have key grater or equal to key_left argument

  2. items have key smaller or equal to key_right argument

  3. items have priority grater or equal to priority_bottom argument

Parameters:

  • key_left – Left bound for query (key is used to compare).

  • key_right – Right bound for query (key is used to compare).

  • priority_bottom – Bottom bound for query (priority is used to compare).

Returns:

list of keys that satisfy criteria, or empty list if no items found

Return type:

List

Complexity:

O(log(N)+K) where N is number of items in PST and K is number of reported items

sorted_query(key_left: _KEY, key_right: _KEY, priority_bottom: _PRIORITY, items_limit: int = 0) → list[source]

Performs 3 sided query on PST.

This function returns list of items that meet the following criteria:

  1. items have key grater or equal to key_left argument

  2. items have key smaller or equal to key_right argument

  3. items have priority grater or equal to priority_bottom argument

Parameters:

  • key_left – Left bound for query (key is used to compare).

  • key_right – Right bound for query (key is used to compare).

  • priority_bottom – Bottom bound for query (priority is used to compare).

  • items_limit (int) – Number of items to return. Default value is 0 - no limit.

Returns:

list of items that satisfy criteria and sorted by priority (in case of limit, items with largest priority will be returned), or empty list if no items found

Return type:

List

Complexity:

O(log(N)+K*log(K)) where N is number of items in PST and K is number of returned items

update_priority(key: _KEY, priority: _PRIORITY) → _PRIORITY[source]

Updates priority for the given key.

Parameters:

  • key – key to update

  • priority – new priority value

Returns:

old priority value

Raises:

KeyError – in case if key not exists in PST

Complexity:

O(log(N)) where N is number of items in PST