Priority search tree data structure
Project description
The priority search tree (PST) is data structure with the following properties:
Items are stored in binary search tree (red-black tree in this case) using tree_key(value) function as a key.
Maintains max heap properties using heap_key(value) function as key.
Ability to perform efficient O(log(N)+K) 3-sided search (finds items with tree_key in interval [min_tree_key,max_tree_key] and heap_key is grater or equal to bottom_heap_key).
For example PST can store 2 dimensional points P(X,Y) using X coordinate as tree_key and Y coordinate as heap_key. Such PST can perform 3 sided search to find points with X in [X_MIN,X_MAX] and Y >= Y_BOTTOM.
Free software: GNU Lesser General Public License v3 or later (LGPLv3+)
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/main.zip
Documentation
Development
To run all the tests run:
tox
Changelog
0.0.0 (2024-03-04)
First release on PyPI.
0.0.1 (2024-03-24)
Initial implementation.
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for priority-search-tree-0.0.1.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6b3268793b8391da057251f07d9b564fe44089b914c0a381380021760e453ee6 |
|
MD5 | 7bfb49d11f5691363958ee60b0a973ad |
|
BLAKE2b-256 | 7c6f742e7821c8ea832f08f72452a0e65aca8530052b8cb33bdc98735abff3e0 |
Hashes for priority_search_tree-0.0.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7b012059ec6ec7b50878f554295cfc7eb4ee13cc7ebadd891fb67d74a8d293b2 |
|
MD5 | 5b6f5660964092f1fa6e5e8796e897d2 |
|
BLAKE2b-256 | 268060d3046f5d87a9d63e81ff019353fbbf7d7d742ebd05af8f638308d37ad7 |