Overview
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+)
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
1 maintainer
Metadata
1 maintainer
Release files for priority-search-tree 0.1.0
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| priority-search-tree-0.1.0.tar.gz | 48.1 kB | Details |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Reset |
|---|---|---|---|---|
| priority_search_tree-0.1.0-py3-none-any.whl | Python 3 | none | any | Details |
Total release size: 73.7 kB
Release files / priority-search-tree-0.1.0.tar.gz
| Download URL | priority-search-tree-0.1.0.tar.gz |
|---|---|
| Size | 48.1 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
dc6d9f892b6620f6e7b88b1ba089775b6ca74109e3e7adca7d9c7f1cd428551c
|
|
BLAKE2b-256 checksum How to use checksums |
c408d107080d3ab2369fbcd5dd449f00965c08810649e18ade1c0078c7d314c0
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/5.0.0 CPython/3.9.19
|
Release files / priority_search_tree-0.1.0-py3-none-any.whl
| Download URL | priority_search_tree-0.1.0-py3-none-any.whl |
|---|---|
| Size | 25.6 kB |
| Tags | Python 3 |
|
SHA-256 checksum How to use checksums |
e169a802373d6dcdd87f4e6cc1aa815187f62d882ffe85a2d5f5f6dc626eaf48
|
|
BLAKE2b-256 checksum How to use checksums |
24d8349ebbd0ac21938d4cce32a419faaf18e80ec5fd2754a5e97f45229116dc
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/5.0.0 CPython/3.9.19
|
