A simple implementation of a binary heap in Rust
This crate implements a simple binary heap from scratch. The aim is to try to keep the implementation easy to understand, even when it implies not using the most efficient algorithms or representations. For a more efficient version, use std::collections::BinaryHeap
.
How to use
- Clone this repository. In the following,
PATH_BH
denotes the path to the cloned repository. - In a Rust project, add
binary_heap = { path = "PATH_BH" }
to the[dependencies]
section of yourCargo.toml
file. - Add
use binary_heap::BinaryHeap;
at the top of each source file where this structure is used.
BinaryHeap
structure
The This crate provides the BinaryHeap
structure, which (as you have probably guessed) is a max binary heap. This structure may be seen as a binary tree which each node holding an element from a partially ordered set satisfying these two properties:
- If a node contains data
$x$ and one of its descendants contains data$y$ , then$y > x$ is false. - At most one level of the tree is incomplete, and this level is filled from left to right.
The BinaryHeap
structure has a type parameter, T
, which must implement the std::cmp::PartialOrd
trait (so that the above inequality makes sense).
In the following, T
is an arbitrary type implementing the std::cmp::PartialOrd
trait.
Main functions
The following functions are implemented for BinaryHeap<T>
:
Function | Condition on T
|
Arguments | Effect | Worst-case asymptotic complexity |
---|---|---|---|---|
new |
None | None | Return a new BinaryHeap<T> . |
|
size |
None | None | Return the number of elements in the heap (usize ). |
|
insert |
None | x: T |
Insert x in the heap. |
|
pop |
None | None | Remove the root element Some(x) ; if the heap is empty, return None . |
|
to_vec |
None | None | Consume the heap and return a vector of all its elements in non-increasing order: if elements T implements std::cmp::Ord , then to_vec is ordered (from maximum to minimum). |
|
get_max |
Clone |
None | Return a copy of the element at the root of the heap. | |
search |
PartialEq |
x: &T |
Return true if the heap contains at least one element y such that *x == y is true or false otherwise. |
Default
trait
The type BinaryHeap<T>
implements the Default
trait; the default value is an empty heap.
Iterator
trait
The type BinaryHeap<T>
implements the Iterator
trait. Elements of the heap are returned in non-increasing order: when going through the iterator, if an element