priority-search-tree

Priority search tree data structure


License
Other
Install
pip install priority-search-tree==0.1.0

Documentation

Overview

docs Documentation Status
tests GitHub Actions Build Status Coverage Status
package PyPI Package latest release PyPI Wheel Supported versions Supported implementations Commits since latest release

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