#median #heap #constant-time #binary-heap #algorithm #running-median

median-heap

A median heap implementation in Rust, used to keep track of a running median of a sequence of numbers

3 releases

0.1.2 Aug 29, 2024
0.1.1 May 17, 2024
0.1.0 May 17, 2024

#850 in Data structures

Download history 11/week @ 2024-07-25 2/week @ 2024-08-01 121/week @ 2024-08-29 16/week @ 2024-09-12 20/week @ 2024-09-19 17/week @ 2024-09-26 3/week @ 2024-10-03

56 downloads per month

MIT license

21KB
355 lines

MedianHeap

MedianHeap is a Rust crate that provides a data structure for calculating the median of a collection of values in constant time. It utilizes two binary heaps to store values efficiently and offers flexibility in calculating the median by allowing different strategies through user-defined traits.

Installation

Add the following line to your Cargo.toml file:

[dependencies]
median_heap = "0.1.0"

Usage

To use MedianHeap, add this to your code:

use median_heap::{MedianHeap, MergeMedian};

struct MyMedian;
impl MergeMedian<i32> for MyMedian {
  fn merge(&self, a: &i32, b: &i32) -> i32 {
    if a > b {
      *a
    } else {
      *b
    }
  }
}

fn main() {
  let mut heap = MedianHeap::new(MyMedian);
  heap.push(1);
  heap.push(2);
  heap.push(3);
  heap.push(4);

  assert_eq!(3, heap.get_median().unwrap()); // Two median candidates are 2 and 3. MyMedian.merge(2, 3) returns 3.
}

License

This project is licensed under the MIT License - see the LICENSE file for details.

Dependencies

~465KB