mut-binary-heap
| Crates.io | mut-binary-heap |
| lib.rs | mut-binary-heap |
| version | 0.1.0 |
| created_at | 2023-03-20 17:25:25.865459+00 |
| updated_at | 2023-03-20 17:25:25.865459+00 |
| description | Enhanced version of std::collections::BinaryHeap that supports increase and decrease key, max, min, and custom-order heaps. |
| homepage | |
| repository | https://github.com/Wasabi375/mut-binary-heap |
| max_upload_size | |
| id | 815493 |
| size | 138,132 |
Burkhard Mittelbach (Wasabi375)
documentation
README
mut-binary-heap
This create provides a binary heap implementation that stores key-value pairs.
The main advantage of that is that unlike with an implementation like
[std::collections::BinaryHeap] checking if any given key exist is O(1) instead of O(n).
Same for getting the value for a given key. This allows for cheap modification of
values within the binary heap. Updating a value is O(log n) iff you have direct access to the value.
For a binary heap that does not store key-value pairs update operations would be O(n) because
they first have to find the value to update. The disadvantage is the additional storage space
required to store a hash map that provides indices into the heap for each key.
Enhancement over Rust's
std::collections::BinaryHeap.
MSRV (Minimum Supported Rust Version)
The minimum supported Rust version is 1.56.0.
Changes
This crate is based on binary-heap-plus
which is itself a based on the standard library's implementation of
BinaryHeap.
Version 0.1.0 provides a thorough refactor to allow storage of key-value pairs as well as retrieval and modification of values.
For more see: CHANGELOG.md.
License
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.