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

median-heap

Rust 中的一种中值堆实现,用于跟踪一系列数字的运行中值。

2 个版本

0.1.1 2024 年 5 月 17 日
0.1.0 2024 年 5 月 17 日

数据结构 中排名第 852

MIT 许可证

21KB
355

MedianHeap

MedianHeap 是一个 Rust 包,提供了一种在常数时间内计算值集合中位数的数据结构。它利用两个二叉堆有效地存储值,并通过允许用户定义特性来计算中值的策略,提供了灵活性。

安装

将以下行添加到您的 Cargo.toml 文件中

[dependencies]
median_heap: "0.1.0"

使用

要使用 MedianHeap,请将以下内容添加到您的代码中

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.
}

许可证

本项目采用 MIT 许可证 - 请参阅 LICENSE 文件以获取详细信息。

依赖项

~465KB