atcoder/lib/data_structure/
heap.rs

1//! 最大ヒープと最小ヒープです。
2
3use std::cmp::Reverse;
4use std::collections::BinaryHeap;
5
6/// [`Ord`] で比較できる要素を、最大値から順に取り出すヒープです。
7///
8/// [`BinaryHeap`] の型エイリアスです。要素の追加・最大値の取り出しは `O(log N)`、
9/// 最大値の参照は `O(1)` です。空のヒープからの `pop` と `peek` は `None` を返します。
10pub type MaxHeap<T> = BinaryHeap<T>;
11
12/// 最小値を優先して取り出すヒープです。
13///
14/// [`push`](Self::push) と [`pop`](Self::pop) は `O(log N)`、[`peek`](Self::peek) は
15/// `O(1)` です。
16///
17/// # Examples
18///
19/// ```
20/// use atcoder::data_structure::heap::MinHeap;
21///
22/// let mut heap = MinHeap::new();
23/// heap.push(3);
24/// heap.push(1);
25/// assert_eq!(heap.pop(), Some(1));
26/// ```
27#[derive(Debug, Clone)]
28pub struct MinHeap<T>(BinaryHeap<Reverse<T>>);
29
30impl<T: Ord> Default for MinHeap<T> {
31    fn default() -> Self {
32        Self::new()
33    }
34}
35
36impl<T: Ord> MinHeap<T> {
37    /// 空の最小ヒープを作ります。計算量は `O(1)` です。
38    pub fn new() -> Self {
39        Self(BinaryHeap::new())
40    }
41
42    /// 要素を追加します。計算量は `O(log N)` です。
43    pub fn push(&mut self, item: T) {
44        self.0.push(Reverse(item));
45    }
46
47    /// 最小要素を削除して返します。空なら `None` です。計算量は `O(log N)` です。
48    pub fn pop(&mut self) -> Option<T> {
49        self.0.pop().map(|Reverse(value)| value)
50    }
51
52    /// 最小要素への参照を返します。空なら `None` です。計算量は `O(1)` です。
53    pub fn peek(&self) -> Option<&T> {
54        self.0.peek().map(|Reverse(value)| value)
55    }
56
57    /// 要素数を返します。計算量は `O(1)` です。
58    pub fn len(&self) -> usize {
59        self.0.len()
60    }
61
62    /// 空なら `true` を返します。計算量は `O(1)` です。
63    pub fn is_empty(&self) -> bool {
64        self.0.is_empty()
65    }
66}
atcoder/lib/data_structure/heap.rs

atcoder/lib/data_structure/
heap.rs
