priority-search-tree 0.1.0

Priority search tree data structure

The priority search tree (PST) is data structure (mutable mapping {key: priority}) with the following properties:

• Keys are stored in binary search tree (red-black tree in this case).

• Maintains max heap properties (can return key with max priority in constant time).

• Ability to perform efficient 3-sided search (finds items with key in interval [min_tree_key,max_tree_key] and priority is grater or equal to bottom_priority).

For example PST can store 2 dimensional points P(X,Y) using X coordinate as key and Y coordinate as priority. Such PST can perform 3 sided search to find points with X in [X_MIN,X_MAX] and Y >= Y_BOTTOM.

Installation

pip install priority-search-tree

You can also install the in-development version with:

pip install https://github.com/yusinv/priority-search-tree/archive/develop.zip

Documentation

https://priority-search-tree.readthedocs.io/

Development

To run all the tests run:

tox

Licence

Free software: GNU Lesser General Public License v3 or later (LGPLv3+)

Changelog

0.0.0 (2024-03-04)

• First release on PyPI.

0.0.1 (2024-03-24)

• Initial implementation.

0.0.2 (2024-03-26)

• Added sorted_query method.

• Added __len__ and __contains__ methods.

• Added clear method.

• Fixed issue with not unique heap keys

0.1.0 (2024-04-08)

• Refactoring

• Added PrioritySearchSet class

• Added __iter__ method