Skip to main content

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

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.

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

priority-search-tree-0.0.1.tar.gz (42.9 kB view hashes)

Uploaded Source

Built Distribution

priority_search_tree-0.0.1-py3-none-any.whl (21.9 kB view hashes)

Uploaded Python 3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page