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.