haar_lib/ds/
skew_heap.rs

1//! 融合可能ヒープ
2
3use std::mem::swap;
4
5#[derive(Debug, Clone)]
6struct Node<T> {
7    value: T,
8    left: Option<Box<Node<T>>>,
9    right: Option<Box<Node<T>>>,
10}
11
12impl<T: Ord> Node<T> {
13    pub fn new(value: T) -> Self {
14        Self {
15            value,
16            left: None,
17            right: None,
18        }
19    }
20
21    pub fn meld(&mut self, other: Option<Box<Node<T>>>) {
22        if let Some(mut other) = other {
23            if self.value < other.value {
24                swap(self, other.as_mut());
25            }
26
27            match self.right.as_mut() {
28                Some(right) => right.meld(Some(other)),
29                None => self.right = Some(other),
30            }
31
32            swap(&mut self.left, &mut self.right);
33        }
34    }
35}
36
37/// 融合可能ヒープ
38#[derive(Debug, Clone, Default)]
39pub struct SkewHeap<T> {
40    root: Option<Box<Node<T>>>,
41    size: usize,
42}
43
44impl<T: Ord> SkewHeap<T> {
45    /// 空の[`SkewHeap<T>`]を生成する。
46    pub fn new() -> Self {
47        Self {
48            root: None,
49            size: 0,
50        }
51    }
52
53    /// 他の`SkewHeap<T>`を融合する。
54    pub fn meld(&mut self, other: SkewHeap<T>) {
55        self.size += other.size;
56        match self.root.as_mut() {
57            None => self.root = other.root,
58            Some(root) => root.meld(other.root),
59        }
60    }
61
62    /// 値`value`を挿入する。
63    pub fn push(&mut self, value: T) {
64        self.size += 1;
65        let t = Some(Box::new(Node::new(value)));
66        match self.root.as_mut() {
67            None => self.root = t,
68            Some(root) => root.meld(t),
69        }
70    }
71
72    /// ヒープの最大値を返す。
73    pub fn peek(&self) -> Option<&T> {
74        self.root.as_ref().map(|x| &x.value)
75    }
76
77    /// 最大値をヒープから削除して、その値を返す。
78    pub fn pop(&mut self) -> Option<T> {
79        match self.root.take() {
80            None => None,
81            Some(root) => {
82                self.size -= 1;
83
84                let Node {
85                    value: x,
86                    left,
87                    right,
88                } = *root;
89                match left {
90                    None => self.root = right,
91                    Some(mut left) => {
92                        left.meld(right);
93                        self.root = Some(left);
94                    }
95                }
96
97                Some(x)
98            }
99        }
100    }
101
102    /// ヒープに含まれている値の個数を返す。
103    pub fn len(&self) -> usize {
104        self.size
105    }
106
107    /// ヒープが空ならば`true`を返す。
108    pub fn is_empty(&self) -> bool {
109        self.size == 0
110    }
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116    use rand::Rng;
117    use std::collections::BinaryHeap;
118
119    #[test]
120    fn test() {
121        let mut heap = SkewHeap::<u32>::new();
122        let mut bheap = BinaryHeap::<u32>::new();
123
124        let mut heap2 = SkewHeap::<u32>::new();
125        let mut bheap2 = BinaryHeap::<u32>::new();
126
127        let mut rng = rand::thread_rng();
128
129        for _ in 0..100 {
130            let x = rng.gen::<u32>();
131            heap.push(x);
132            bheap.push(x);
133        }
134
135        for _ in 0..100 {
136            let x = rng.gen::<u32>();
137            heap2.push(x);
138            bheap2.push(x);
139        }
140
141        heap.meld(heap2);
142
143        while let Some(x) = bheap2.pop() {
144            bheap.push(x);
145        }
146
147        while let (Some(x), Some(y)) = (heap.pop(), bheap.pop()) {
148            assert_eq!(x, y);
149        }
150    }
151}
haar_lib/ds/skew_heap.rs

haar_lib/ds/
skew_heap.rs
