Overview¶
docs |
|
|---|---|
tests |
|
package |
|
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¶
Development¶
To run all the tests run:
tox
Licence¶
Free software: GNU Lesser General Public License v3 or later (LGPLv3+)