priority-search-tree 0.0.1

Priority search tree data structure

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

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

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.