Struct PairingHeap

Source

pub struct PairingHeap<T, C = Less, A = EmptyAct<T>>where
    A: MonoidAct<Key = T, Act: PartialEq>,{
    root: Option<Box<Node<T, A>>>,
    len: usize,
    cmp: C,
}

Fields§

§root: Option<Box<Node<T, A>>>§len: usize§cmp: C

Implementations§

Source §

impl<T, C, A> PairingHeap<T, C, A>
where C: Comparator<T>, A: MonoidAct<Key = T, Act: PartialEq>,

Source

pub fn with_comparator(cmp: C) -> Self

Examples found in repository ?

crates/competitive/src/data_structure/pairing_heap.rs (line 212)

211    fn default() -> Self {
212        Self::with_comparator(C::default())
213    }

Source

pub fn len(&self) -> usize

Examples found in repository ?

crates/competitive/src/data_structure/pairing_heap.rs (line 354)

353    fn size_hint(&self) -> (usize, Option<usize>) {
354        let len = self.heap.len();
355        (len, Some(len))
356    }
357}
358
359impl<T, C, A> ExactSizeIterator for IntoIter<T, C, A>
360where
361    C: Comparator<T>,
362    A: MonoidAct<Key = T, Act: PartialEq>,
363{
364    fn len(&self) -> usize {
365        self.heap.len()
366    }

Source

pub fn is_empty(&self) -> bool

Examples found in repository ?

crates/competitive/src/data_structure/pairing_heap.rs (line 110)

109    pub fn append(&mut self, other: &mut Self) {
110        if other.is_empty() {
111            return;
112        }
113
114        let left = self.root.take();
115        self.root = self.merge_option(left, other.root.take());
116        self.len += other.len;
117        other.len = 0;
118    }

Source

pub fn peek(&self) -> Option<&T>

Source

pub fn push(&mut self, value: T)

Examples found in repository ?

crates/competitive/src/data_structure/pairing_heap.rs (line 248)

246    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
247        for value in iter {
248            self.push(value);
249        }
250    }

More examples

Hide additional examples

crates/competitive/src/graph/minimum_spanning_arborescence.rs (line 39)

5    pub fn minimum_spanning_arborescence<G, F>(
6        &self,
7        root: usize,
8        weight: F,
9    ) -> Option<(G::T, Vec<usize>)>
10    where
11        G: Group<T: Ord>,
12        F: Fn(usize) -> G::T,
13    {
14        struct WeightAct<G>(std::marker::PhantomData<fn() -> G>);
15        impl<G> MonoidAct for WeightAct<G>
16        where
17            G: Group,
18        {
19            type Key = (G::T, usize);
20            type Act = G::T;
21            type ActMonoid = G;
22
23            fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
24                (G::operate(&x.0, a), x.1)
25            }
26
27            fn act_assign(x: &mut Self::Key, a: &Self::Act) {
28                x.0 = G::operate(&x.0, a);
29            }
30        }
31        let mut uf = MergingUnionFind::new_with_merger(
32            self.vertices_size(),
33            |_| PairingHeap::<(G::T, usize), Less, WeightAct<G>>::default(),
34            |x, y| x.append(y),
35        );
36        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
37        state[root] = 2;
38        for (id, &(_, to)) in self.edges().enumerate() {
39            uf.merge_data_mut(to).push((weight(id), id));
40        }
41        let mut paredge = vec![0; self.edges_size()];
42        let mut ord = vec![];
43        let mut leaf = vec![self.edges_size(); self.vertices_size()];
44        let mut cycle = 0usize;
45        let mut acc = G::unit();
46        for mut cur in self.vertices() {
47            if state[cur] != 0 {
48                continue;
49            }
50            let mut path = vec![];
51            let mut ch = vec![];
52            while state[cur] != 2 {
53                path.push(cur);
54                state[cur] = 1;
55                let (w, eid) = {
56                    match uf.merge_data_mut(cur).pop() {
57                        Some((w, eid)) => (w, eid),
58                        None => return None,
59                    }
60                };
61                uf.merge_data_mut(cur).apply_all(G::inverse(&w));
62                acc = G::operate(&acc, &w);
63                ord.push(eid);
64                let (u, v) = self[eid];
65                if leaf[v] >= self.edges_size() {
66                    leaf[v] = eid;
67                }
68                while cycle > 0 {
69                    paredge[ch.pop().unwrap()] = eid;
70                    cycle -= 1;
71                }
72                ch.push(eid);
73                if state[uf.find_root(u)] == 1 {
74                    while let Some(t) = path.pop() {
75                        state[t] = 2;
76                        cycle += 1;
77                        if !uf.unite(u, t) {
78                            break;
79                        }
80                    }
81                    state[uf.find_root(u)] = 1;
82                }
83                cur = uf.find_root(u);
84            }
85            for u in path.into_iter() {
86                state[u] = 2;
87            }
88        }
89        let mut tree = vec![root; self.vertices_size()];
90        let mut used = vec![false; self.edges_size()];
91        for eid in ord.into_iter().rev() {
92            if !used[eid] {
93                let (u, v) = self[eid];
94                tree[v] = u;
95                let mut x = leaf[v];
96                while x != eid {
97                    used[x] = true;
98                    x = paredge[x];
99                }
100            }
101        }
102        Some((acc, tree))
103    }

Source

pub fn append(&mut self, other: &mut Self)

Examples found in repository ?

crates/competitive/src/graph/minimum_spanning_arborescence.rs (line 34)

5    pub fn minimum_spanning_arborescence<G, F>(
6        &self,
7        root: usize,
8        weight: F,
9    ) -> Option<(G::T, Vec<usize>)>
10    where
11        G: Group<T: Ord>,
12        F: Fn(usize) -> G::T,
13    {
14        struct WeightAct<G>(std::marker::PhantomData<fn() -> G>);
15        impl<G> MonoidAct for WeightAct<G>
16        where
17            G: Group,
18        {
19            type Key = (G::T, usize);
20            type Act = G::T;
21            type ActMonoid = G;
22
23            fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
24                (G::operate(&x.0, a), x.1)
25            }
26
27            fn act_assign(x: &mut Self::Key, a: &Self::Act) {
28                x.0 = G::operate(&x.0, a);
29            }
30        }
31        let mut uf = MergingUnionFind::new_with_merger(
32            self.vertices_size(),
33            |_| PairingHeap::<(G::T, usize), Less, WeightAct<G>>::default(),
34            |x, y| x.append(y),
35        );
36        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
37        state[root] = 2;
38        for (id, &(_, to)) in self.edges().enumerate() {
39            uf.merge_data_mut(to).push((weight(id), id));
40        }
41        let mut paredge = vec![0; self.edges_size()];
42        let mut ord = vec![];
43        let mut leaf = vec![self.edges_size(); self.vertices_size()];
44        let mut cycle = 0usize;
45        let mut acc = G::unit();
46        for mut cur in self.vertices() {
47            if state[cur] != 0 {
48                continue;
49            }
50            let mut path = vec![];
51            let mut ch = vec![];
52            while state[cur] != 2 {
53                path.push(cur);
54                state[cur] = 1;
55                let (w, eid) = {
56                    match uf.merge_data_mut(cur).pop() {
57                        Some((w, eid)) => (w, eid),
58                        None => return None,
59                    }
60                };
61                uf.merge_data_mut(cur).apply_all(G::inverse(&w));
62                acc = G::operate(&acc, &w);
63                ord.push(eid);
64                let (u, v) = self[eid];
65                if leaf[v] >= self.edges_size() {
66                    leaf[v] = eid;
67                }
68                while cycle > 0 {
69                    paredge[ch.pop().unwrap()] = eid;
70                    cycle -= 1;
71                }
72                ch.push(eid);
73                if state[uf.find_root(u)] == 1 {
74                    while let Some(t) = path.pop() {
75                        state[t] = 2;
76                        cycle += 1;
77                        if !uf.unite(u, t) {
78                            break;
79                        }
80                    }
81                    state[uf.find_root(u)] = 1;
82                }
83                cur = uf.find_root(u);
84            }
85            for u in path.into_iter() {
86                state[u] = 2;
87            }
88        }
89        let mut tree = vec![root; self.vertices_size()];
90        let mut used = vec![false; self.edges_size()];
91        for eid in ord.into_iter().rev() {
92            if !used[eid] {
93                let (u, v) = self[eid];
94                tree[v] = u;
95                let mut x = leaf[v];
96                while x != eid {
97                    used[x] = true;
98                    x = paredge[x];
99                }
100            }
101        }
102        Some((acc, tree))
103    }

Source

pub fn pop(&mut self) -> Option<T>

Examples found in repository ?

crates/competitive/src/data_structure/pairing_heap.rs (line 156)

154    pub fn into_sorted_vec(mut self) -> Vec<T> {
155        let mut result = Vec::with_capacity(self.len);
156        while let Some(value) = self.pop() {
157            result.push(value);
158        }
159        result
160    }
161
162    fn merge_option(
163        &mut self,
164        a: Option<Box<Node<T, A>>>,
165        b: Option<Box<Node<T, A>>>,
166    ) -> Option<Box<Node<T, A>>> {
167        match (a, b) {
168            (None, None) => None,
169            (Some(node), None) | (None, Some(node)) => Some(node),
170            (Some(mut a), Some(mut b)) => {
171                a.propagate();
172                b.propagate();
173                if self.cmp.compare(&a.value, &b.value) == Ordering::Greater {
174                    swap(&mut a, &mut b);
175                }
176                b.next_sibling = a.first_child.take();
177                a.first_child = Some(b);
178                Some(a)
179            }
180        }
181    }
182
183    fn merge_pairs(&mut self, mut head: Option<Box<Node<T, A>>>) -> Option<Box<Node<T, A>>> {
184        let mut pairs: Vec<Box<Node<T, A>>> = Vec::new();
185        while let Some(mut first) = head {
186            first.propagate();
187            let next = first.next_sibling.take();
188            if let Some(mut second) = next {
189                second.propagate();
190                head = second.next_sibling.take();
191                pairs.push(self.merge_option(Some(first), Some(second)).unwrap());
192            } else {
193                pairs.push(first);
194                break;
195            }
196        }
197
198        let mut result = None;
199        while let Some(node) = pairs.pop() {
200            result = self.merge_option(Some(node), result);
201        }
202        result
203    }
204}
205
206impl<T, C, A> Default for PairingHeap<T, C, A>
207where
208    C: Comparator<T> + Default,
209    A: MonoidAct<Key = T, Act: PartialEq>,
210{
211    fn default() -> Self {
212        Self::with_comparator(C::default())
213    }
214}
215
216impl<T, A> PairingHeap<T, Less, A>
217where
218    T: Ord,
219    A: MonoidAct<Key = T, Act: PartialEq>,
220{
221    pub fn new() -> Self {
222        Self::default()
223    }
224}
225
226impl<T, C, A> Debug for PairingHeap<T, C, A>
227where
228    T: Debug,
229    C: Debug + Comparator<T>,
230    A: MonoidAct<Key = T, Act: PartialEq + Debug>,
231{
232    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
233        f.debug_struct("PairingHeap")
234            .field("len", &self.len)
235            .field("root", &self.root)
236            .field("cmp", &self.cmp)
237            .finish()
238    }
239}
240
241impl<T, C, A> Extend<T> for PairingHeap<T, C, A>
242where
243    C: Comparator<T>,
244    A: MonoidAct<Key = T, Act: PartialEq>,
245{
246    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
247        for value in iter {
248            self.push(value);
249        }
250    }
251}
252
253impl<T, C, A> FromIterator<T> for PairingHeap<T, C, A>
254where
255    C: Comparator<T> + Default,
256    A: MonoidAct<Key = T, Act: PartialEq>,
257{
258    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
259        let mut heap = Self::default();
260        heap.extend(iter);
261        heap
262    }
263}
264
265pub struct PeekMut<'a, T, C = Less, A = EmptyAct<T>>
266where
267    C: Comparator<T>,
268    A: MonoidAct<Key = T, Act: PartialEq>,
269{
270    heap: &'a mut PairingHeap<T, C, A>,
271    node: Option<Box<Node<T, A>>>,
272}
273
274impl<'a, T, C, A> PeekMut<'a, T, C, A>
275where
276    C: Comparator<T>,
277    A: MonoidAct<Key = T, Act: PartialEq>,
278{
279    pub fn pop(mut this: Self) -> T {
280        this.heap.len -= 1;
281        let node = this.node.take().expect("PeekMut already consumed");
282        let Node { value, .. } = *node;
283        value
284    }
285}
286
287impl<'a, T, C, A> Deref for PeekMut<'a, T, C, A>
288where
289    C: Comparator<T>,
290    A: MonoidAct<Key = T, Act: PartialEq>,
291{
292    type Target = T;
293
294    fn deref(&self) -> &Self::Target {
295        &self.node.as_ref().expect("PeekMut already consumed").value
296    }
297}
298
299impl<'a, T, C, A> DerefMut for PeekMut<'a, T, C, A>
300where
301    C: Comparator<T>,
302    A: MonoidAct<Key = T, Act: PartialEq>,
303{
304    fn deref_mut(&mut self) -> &mut Self::Target {
305        &mut self.node.as_mut().expect("PeekMut already consumed").value
306    }
307}
308
309impl<'a, T, C, A> Drop for PeekMut<'a, T, C, A>
310where
311    C: Comparator<T>,
312    A: MonoidAct<Key = T, Act: PartialEq>,
313{
314    fn drop(&mut self) {
315        if let Some(mut node) = self.node.take() {
316            debug_assert!(node.next_sibling.is_none());
317            let root = self.heap.root.take();
318            node.first_child = None;
319            self.heap.root = self.heap.merge_option(root, Some(node));
320        }
321    }
322}
323
324pub struct IntoIter<T, C = Less, A = EmptyAct<T>>
325where
326    C: Comparator<T>,
327    A: MonoidAct<Key = T, Act: PartialEq>,
328{
329    heap: PairingHeap<T, C, A>,
330}
331
332impl<T, C, A> IntoIter<T, C, A>
333where
334    C: Comparator<T>,
335    A: MonoidAct<Key = T, Act: PartialEq>,
336{
337    fn new(heap: PairingHeap<T, C, A>) -> Self {
338        Self { heap }
339    }
340}
341
342impl<T, C, A> Iterator for IntoIter<T, C, A>
343where
344    C: Comparator<T>,
345    A: MonoidAct<Key = T, Act: PartialEq>,
346{
347    type Item = T;
348
349    fn next(&mut self) -> Option<Self::Item> {
350        self.heap.pop()
351    }

More examples

Hide additional examples

crates/competitive/src/graph/minimum_spanning_arborescence.rs (line 56)

5    pub fn minimum_spanning_arborescence<G, F>(
6        &self,
7        root: usize,
8        weight: F,
9    ) -> Option<(G::T, Vec<usize>)>
10    where
11        G: Group<T: Ord>,
12        F: Fn(usize) -> G::T,
13    {
14        struct WeightAct<G>(std::marker::PhantomData<fn() -> G>);
15        impl<G> MonoidAct for WeightAct<G>
16        where
17            G: Group,
18        {
19            type Key = (G::T, usize);
20            type Act = G::T;
21            type ActMonoid = G;
22
23            fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
24                (G::operate(&x.0, a), x.1)
25            }
26
27            fn act_assign(x: &mut Self::Key, a: &Self::Act) {
28                x.0 = G::operate(&x.0, a);
29            }
30        }
31        let mut uf = MergingUnionFind::new_with_merger(
32            self.vertices_size(),
33            |_| PairingHeap::<(G::T, usize), Less, WeightAct<G>>::default(),
34            |x, y| x.append(y),
35        );
36        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
37        state[root] = 2;
38        for (id, &(_, to)) in self.edges().enumerate() {
39            uf.merge_data_mut(to).push((weight(id), id));
40        }
41        let mut paredge = vec![0; self.edges_size()];
42        let mut ord = vec![];
43        let mut leaf = vec![self.edges_size(); self.vertices_size()];
44        let mut cycle = 0usize;
45        let mut acc = G::unit();
46        for mut cur in self.vertices() {
47            if state[cur] != 0 {
48                continue;
49            }
50            let mut path = vec![];
51            let mut ch = vec![];
52            while state[cur] != 2 {
53                path.push(cur);
54                state[cur] = 1;
55                let (w, eid) = {
56                    match uf.merge_data_mut(cur).pop() {
57                        Some((w, eid)) => (w, eid),
58                        None => return None,
59                    }
60                };
61                uf.merge_data_mut(cur).apply_all(G::inverse(&w));
62                acc = G::operate(&acc, &w);
63                ord.push(eid);
64                let (u, v) = self[eid];
65                if leaf[v] >= self.edges_size() {
66                    leaf[v] = eid;
67                }
68                while cycle > 0 {
69                    paredge[ch.pop().unwrap()] = eid;
70                    cycle -= 1;
71                }
72                ch.push(eid);
73                if state[uf.find_root(u)] == 1 {
74                    while let Some(t) = path.pop() {
75                        state[t] = 2;
76                        cycle += 1;
77                        if !uf.unite(u, t) {
78                            break;
79                        }
80                    }
81                    state[uf.find_root(u)] = 1;
82                }
83                cur = uf.find_root(u);
84            }
85            for u in path.into_iter() {
86                state[u] = 2;
87            }
88        }
89        let mut tree = vec![root; self.vertices_size()];
90        let mut used = vec![false; self.edges_size()];
91        for eid in ord.into_iter().rev() {
92            if !used[eid] {
93                let (u, v) = self[eid];
94                tree[v] = u;
95                let mut x = leaf[v];
96                while x != eid {
97                    used[x] = true;
98                    x = paredge[x];
99                }
100            }
101        }
102        Some((acc, tree))
103    }

Source

pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T, C, A>>

Source

pub fn clear(&mut self)

Source

pub fn apply_all(&mut self, act: A::Act)

Examples found in repository ?

crates/competitive/src/graph/minimum_spanning_arborescence.rs (line 61)

5    pub fn minimum_spanning_arborescence<G, F>(
6        &self,
7        root: usize,
8        weight: F,
9    ) -> Option<(G::T, Vec<usize>)>
10    where
11        G: Group<T: Ord>,
12        F: Fn(usize) -> G::T,
13    {
14        struct WeightAct<G>(std::marker::PhantomData<fn() -> G>);
15        impl<G> MonoidAct for WeightAct<G>
16        where
17            G: Group,
18        {
19            type Key = (G::T, usize);
20            type Act = G::T;
21            type ActMonoid = G;
22
23            fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
24                (G::operate(&x.0, a), x.1)
25            }
26
27            fn act_assign(x: &mut Self::Key, a: &Self::Act) {
28                x.0 = G::operate(&x.0, a);
29            }
30        }
31        let mut uf = MergingUnionFind::new_with_merger(
32            self.vertices_size(),
33            |_| PairingHeap::<(G::T, usize), Less, WeightAct<G>>::default(),
34            |x, y| x.append(y),
35        );
36        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
37        state[root] = 2;
38        for (id, &(_, to)) in self.edges().enumerate() {
39            uf.merge_data_mut(to).push((weight(id), id));
40        }
41        let mut paredge = vec![0; self.edges_size()];
42        let mut ord = vec![];
43        let mut leaf = vec![self.edges_size(); self.vertices_size()];
44        let mut cycle = 0usize;
45        let mut acc = G::unit();
46        for mut cur in self.vertices() {
47            if state[cur] != 0 {
48                continue;
49            }
50            let mut path = vec![];
51            let mut ch = vec![];
52            while state[cur] != 2 {
53                path.push(cur);
54                state[cur] = 1;
55                let (w, eid) = {
56                    match uf.merge_data_mut(cur).pop() {
57                        Some((w, eid)) => (w, eid),
58                        None => return None,
59                    }
60                };
61                uf.merge_data_mut(cur).apply_all(G::inverse(&w));
62                acc = G::operate(&acc, &w);
63                ord.push(eid);
64                let (u, v) = self[eid];
65                if leaf[v] >= self.edges_size() {
66                    leaf[v] = eid;
67                }
68                while cycle > 0 {
69                    paredge[ch.pop().unwrap()] = eid;
70                    cycle -= 1;
71                }
72                ch.push(eid);
73                if state[uf.find_root(u)] == 1 {
74                    while let Some(t) = path.pop() {
75                        state[t] = 2;
76                        cycle += 1;
77                        if !uf.unite(u, t) {
78                            break;
79                        }
80                    }
81                    state[uf.find_root(u)] = 1;
82                }
83                cur = uf.find_root(u);
84            }
85            for u in path.into_iter() {
86                state[u] = 2;
87            }
88        }
89        let mut tree = vec![root; self.vertices_size()];
90        let mut used = vec![false; self.edges_size()];
91        for eid in ord.into_iter().rev() {
92            if !used[eid] {
93                let (u, v) = self[eid];
94                tree[v] = u;
95                let mut x = leaf[v];
96                while x != eid {
97                    used[x] = true;
98                    x = paredge[x];
99                }
100            }
101        }
102        Some((acc, tree))
103    }

Source

pub fn into_sorted_vec(self) -> Vec<T>

Source

fn merge_option( &mut self, a: Option<Box<Node<T, A>>>, b: Option<Box<Node<T, A>>>, ) -> Option<Box<Node<T, A>>>

Examples found in repository ?

crates/competitive/src/data_structure/pairing_heap.rs (line 105)

102    pub fn push(&mut self, value: T) {
103        let node = Box::new(Node::new(value));
104        let root = self.root.take();
105        self.root = self.merge_option(root, Some(node));
106        self.len += 1;
107    }
108
109    pub fn append(&mut self, other: &mut Self) {
110        if other.is_empty() {
111            return;
112        }
113
114        let left = self.root.take();
115        self.root = self.merge_option(left, other.root.take());
116        self.len += other.len;
117        other.len = 0;
118    }
119
120    pub fn pop(&mut self) -> Option<T> {
121        self.root.take().map(|mut root| {
122            self.len -= 1;
123            root.propagate();
124            let children = root.first_child.take();
125            self.root = self.merge_pairs(children);
126            root.value
127        })
128    }
129
130    pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T, C, A>> {
131        let mut root = self.root.take()?;
132        root.propagate();
133        let children = root.first_child.take();
134        debug_assert!(root.next_sibling.is_none());
135        root.next_sibling = None;
136        self.root = self.merge_pairs(children);
137        Some(PeekMut {
138            heap: self,
139            node: Some(root),
140        })
141    }
142
143    pub fn clear(&mut self) {
144        self.root = None;
145        self.len = 0;
146    }
147
148    pub fn apply_all(&mut self, act: A::Act) {
149        if let Some(root) = self.root.as_mut() {
150            root.apply(&act);
151        }
152    }
153
154    pub fn into_sorted_vec(mut self) -> Vec<T> {
155        let mut result = Vec::with_capacity(self.len);
156        while let Some(value) = self.pop() {
157            result.push(value);
158        }
159        result
160    }
161
162    fn merge_option(
163        &mut self,
164        a: Option<Box<Node<T, A>>>,
165        b: Option<Box<Node<T, A>>>,
166    ) -> Option<Box<Node<T, A>>> {
167        match (a, b) {
168            (None, None) => None,
169            (Some(node), None) | (None, Some(node)) => Some(node),
170            (Some(mut a), Some(mut b)) => {
171                a.propagate();
172                b.propagate();
173                if self.cmp.compare(&a.value, &b.value) == Ordering::Greater {
174                    swap(&mut a, &mut b);
175                }
176                b.next_sibling = a.first_child.take();
177                a.first_child = Some(b);
178                Some(a)
179            }
180        }
181    }
182
183    fn merge_pairs(&mut self, mut head: Option<Box<Node<T, A>>>) -> Option<Box<Node<T, A>>> {
184        let mut pairs: Vec<Box<Node<T, A>>> = Vec::new();
185        while let Some(mut first) = head {
186            first.propagate();
187            let next = first.next_sibling.take();
188            if let Some(mut second) = next {
189                second.propagate();
190                head = second.next_sibling.take();
191                pairs.push(self.merge_option(Some(first), Some(second)).unwrap());
192            } else {
193                pairs.push(first);
194                break;
195            }
196        }
197
198        let mut result = None;
199        while let Some(node) = pairs.pop() {
200            result = self.merge_option(Some(node), result);
201        }
202        result
203    }
204}
205
206impl<T, C, A> Default for PairingHeap<T, C, A>
207where
208    C: Comparator<T> + Default,
209    A: MonoidAct<Key = T, Act: PartialEq>,
210{
211    fn default() -> Self {
212        Self::with_comparator(C::default())
213    }
214}
215
216impl<T, A> PairingHeap<T, Less, A>
217where
218    T: Ord,
219    A: MonoidAct<Key = T, Act: PartialEq>,
220{
221    pub fn new() -> Self {
222        Self::default()
223    }
224}
225
226impl<T, C, A> Debug for PairingHeap<T, C, A>
227where
228    T: Debug,
229    C: Debug + Comparator<T>,
230    A: MonoidAct<Key = T, Act: PartialEq + Debug>,
231{
232    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
233        f.debug_struct("PairingHeap")
234            .field("len", &self.len)
235            .field("root", &self.root)
236            .field("cmp", &self.cmp)
237            .finish()
238    }
239}
240
241impl<T, C, A> Extend<T> for PairingHeap<T, C, A>
242where
243    C: Comparator<T>,
244    A: MonoidAct<Key = T, Act: PartialEq>,
245{
246    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
247        for value in iter {
248            self.push(value);
249        }
250    }
251}
252
253impl<T, C, A> FromIterator<T> for PairingHeap<T, C, A>
254where
255    C: Comparator<T> + Default,
256    A: MonoidAct<Key = T, Act: PartialEq>,
257{
258    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
259        let mut heap = Self::default();
260        heap.extend(iter);
261        heap
262    }
263}
264
265pub struct PeekMut<'a, T, C = Less, A = EmptyAct<T>>
266where
267    C: Comparator<T>,
268    A: MonoidAct<Key = T, Act: PartialEq>,
269{
270    heap: &'a mut PairingHeap<T, C, A>,
271    node: Option<Box<Node<T, A>>>,
272}
273
274impl<'a, T, C, A> PeekMut<'a, T, C, A>
275where
276    C: Comparator<T>,
277    A: MonoidAct<Key = T, Act: PartialEq>,
278{
279    pub fn pop(mut this: Self) -> T {
280        this.heap.len -= 1;
281        let node = this.node.take().expect("PeekMut already consumed");
282        let Node { value, .. } = *node;
283        value
284    }
285}
286
287impl<'a, T, C, A> Deref for PeekMut<'a, T, C, A>
288where
289    C: Comparator<T>,
290    A: MonoidAct<Key = T, Act: PartialEq>,
291{
292    type Target = T;
293
294    fn deref(&self) -> &Self::Target {
295        &self.node.as_ref().expect("PeekMut already consumed").value
296    }
297}
298
299impl<'a, T, C, A> DerefMut for PeekMut<'a, T, C, A>
300where
301    C: Comparator<T>,
302    A: MonoidAct<Key = T, Act: PartialEq>,
303{
304    fn deref_mut(&mut self) -> &mut Self::Target {
305        &mut self.node.as_mut().expect("PeekMut already consumed").value
306    }
307}
308
309impl<'a, T, C, A> Drop for PeekMut<'a, T, C, A>
310where
311    C: Comparator<T>,
312    A: MonoidAct<Key = T, Act: PartialEq>,
313{
314    fn drop(&mut self) {
315        if let Some(mut node) = self.node.take() {
316            debug_assert!(node.next_sibling.is_none());
317            let root = self.heap.root.take();
318            node.first_child = None;
319            self.heap.root = self.heap.merge_option(root, Some(node));
320        }
321    }

Source

fn merge_pairs( &mut self, head: Option<Box<Node<T, A>>>, ) -> Option<Box<Node<T, A>>>

Examples found in repository ?

crates/competitive/src/data_structure/pairing_heap.rs (line 125)

120    pub fn pop(&mut self) -> Option<T> {
121        self.root.take().map(|mut root| {
122            self.len -= 1;
123            root.propagate();
124            let children = root.first_child.take();
125            self.root = self.merge_pairs(children);
126            root.value
127        })
128    }
129
130    pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T, C, A>> {
131        let mut root = self.root.take()?;
132        root.propagate();
133        let children = root.first_child.take();
134        debug_assert!(root.next_sibling.is_none());
135        root.next_sibling = None;
136        self.root = self.merge_pairs(children);
137        Some(PeekMut {
138            heap: self,
139            node: Some(root),
140        })
141    }

Source §

impl<T, A> PairingHeap<T, Less, A>
where T: Ord, A: MonoidAct<Key = T, Act: PartialEq>,

Source

pub fn new() -> Self

Trait Implementations§

Source §

impl<T: Clone, C: Clone, A> Clone for PairingHeap<T, C, A>
where A: MonoidAct<Key = T, Act: PartialEq> + Clone,

Source §

fn clone(&self) -> PairingHeap<T, C, A>

Returns a duplicate of the value. Read more

1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more

Source §

impl<T, C, A> Debug for PairingHeap<T, C, A>
where T: Debug, C: Debug + Comparator<T>, A: MonoidAct<Key = T, Act: PartialEq + Debug>,

Source §

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Source §

impl<T, C, A> Default for PairingHeap<T, C, A>
where C: Comparator<T> + Default, A: MonoidAct<Key = T, Act: PartialEq>,

Source §

fn default() -> Self

Returns the “default value” for a type. Read more

Source §

impl<T, C, A> Extend<T> for PairingHeap<T, C, A>
where C: Comparator<T>, A: MonoidAct<Key = T, Act: PartialEq>,

Source §

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator. Read more

Source §

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

Source §

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements. Read more

Source §

impl<T, C, A> FromIterator<T> for PairingHeap<T, C, A>
where C: Comparator<T> + Default, A: MonoidAct<Key = T, Act: PartialEq>,

Source §

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator. Read more

Source §

impl<T, C, A> IntoIterator for PairingHeap<T, C, A>
where C: Comparator<T>, A: MonoidAct<Key = T, Act: PartialEq>,

Source §

type Item = T

The type of the elements being iterated over.

Source §

type IntoIter = IntoIter<T, C, A>

Which kind of iterator are we turning this into?

Source §

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more

Auto Trait Implementations§

§

impl<T, C, A> Freeze for PairingHeap<T, C, A>
where C: Freeze,

§

impl<T, C, A> RefUnwindSafe for PairingHeap<T, C, A>
where C: RefUnwindSafe, T: RefUnwindSafe, <A as MonoidAct>::Act: RefUnwindSafe,

§

impl<T, C, A> Send for PairingHeap<T, C, A>
where C: Send, T: Send, <A as MonoidAct>::Act: Send,

§

impl<T, C, A> Sync for PairingHeap<T, C, A>
where C: Sync, T: Sync, <A as MonoidAct>::Act: Sync,

§

impl<T, C, A> Unpin for PairingHeap<T, C, A>
where C: Unpin,

§

impl<T, C, A> UnwindSafe for PairingHeap<T, C, A>
where C: UnwindSafe, T: UnwindSafe, <A as MonoidAct>::Act: UnwindSafe,

Blanket Implementations§

Source §

impl<T> Any for T
where T: 'static + ?Sized,

Source §

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more

Source §

impl<T> Borrow<T> for T
where T: ?Sized,

Source §

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more

Source §

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source §

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more

Source §

impl<T> CloneToUninit for T
where T: Clone,

Source §

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)

Performs copy-assignment from self to dest. Read more

Source §

impl<T> From<T> for T

Source §

fn from(t: T) -> T

Returns the argument unchanged.

Source §

impl<T, U> Into for T
where U: From<T>,

Source §

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source §

impl<T> ToOwned for T
where T: Clone,

Source §

type Owned = T

The resulting type after obtaining ownership.

Source §

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more

Source §

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more

Source §

impl<T, U> TryFrom for T
where U: Into<T>,

Source §

type Error = Infallible

The type returned in the event of a conversion error.

Source §

fn try_from(value: U) -> Result<T, <T as TryFrom>::Error>

Performs the conversion.

Source §

impl<T, U> TryInto for T
where U: TryFrom<T>,

Source §

type Error = >::Error

The type returned in the event of a conversion error.

Source §

fn try_into(self) -> Result<U, >::Error>

Performs the conversion.

Struct PairingHeap Copy item path

Fields§

Implementations§

impl<T, C, A> PairingHeap<T, C, A>where C: Comparator<T>, A: MonoidAct<Key = T, Act: PartialEq>,

pub fn with_comparator(cmp: C) -> Self

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn peek(&self) -> Option<&T>

pub fn push(&mut self, value: T)

pub fn append(&mut self, other: &mut Self)

pub fn pop(&mut self) -> Option<T>

pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T, C, A>>

pub fn clear(&mut self)

pub fn apply_all(&mut self, act: A::Act)

pub fn into_sorted_vec(self) -> Vec<T>

fn merge_option( &mut self, a: Option<Box<Node<T, A>>>, b: Option<Box<Node<T, A>>>, ) -> Option<Box<Node<T, A>>>

fn merge_pairs( &mut self, head: Option<Box<Node<T, A>>>, ) -> Option<Box<Node<T, A>>>

impl<T, A> PairingHeap<T, Less, A>where T: Ord, A: MonoidAct<Key = T, Act: PartialEq>,

pub fn new() -> Self

Trait Implementations§

impl<T: Clone, C: Clone, A> Clone for PairingHeap<T, C, A>where A: MonoidAct<Key = T, Act: PartialEq> + Clone,

fn clone(&self) -> PairingHeap<T, C, A>

fn clone_from(&mut self, source: &Self)

impl<T, C, A> Debug for PairingHeap<T, C, A>where T: Debug, C: Debug + Comparator<T>, A: MonoidAct<Key = T, Act: PartialEq + Debug>,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

impl<T, C, A> Default for PairingHeap<T, C, A>where C: Comparator<T> + Default, A: MonoidAct<Key = T, Act: PartialEq>,

fn default() -> Self

impl<T, C, A> Extend<T> for PairingHeap<T, C, A>where C: Comparator<T>, A: MonoidAct<Key = T, Act: PartialEq>,

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

fn extend_one(&mut self, item: A)

fn extend_reserve(&mut self, additional: usize)

impl<T, C, A> FromIterator<T> for PairingHeap<T, C, A>where C: Comparator<T> + Default, A: MonoidAct<Key = T, Act: PartialEq>,

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

impl<T, C, A> IntoIterator for PairingHeap<T, C, A>where C: Comparator<T>, A: MonoidAct<Key = T, Act: PartialEq>,

type Item = T

type IntoIter = IntoIter<T, C, A>

fn into_iter(self) -> Self::IntoIter

Auto Trait Implementations§

impl<T, C, A> Freeze for PairingHeap<T, C, A>where C: Freeze,

impl<T, C, A> RefUnwindSafe for PairingHeap<T, C, A>where C: RefUnwindSafe, T: RefUnwindSafe, <A as MonoidAct>::Act: RefUnwindSafe,

impl<T, C, A> Send for PairingHeap<T, C, A>where C: Send, T: Send, <A as MonoidAct>::Act: Send,

impl<T, C, A> Sync for PairingHeap<T, C, A>where C: Sync, T: Sync, <A as MonoidAct>::Act: Sync,

impl<T, C, A> Unpin for PairingHeap<T, C, A>where C: Unpin,

impl<T, C, A> UnwindSafe for PairingHeap<T, C, A>where C: UnwindSafe, T: UnwindSafe, <A as MonoidAct>::Act: UnwindSafe,

Blanket Implementations§

impl<T> Any for Twhere T: 'static + ?Sized,

fn type_id(&self) -> TypeId

impl<T> Borrow<T> for Twhere T: ?Sized,

fn borrow(&self) -> &T

impl<T> BorrowMut<T> for Twhere T: ?Sized,

fn borrow_mut(&mut self) -> &mut T

impl<T> CloneToUninit for Twhere T: Clone,

unsafe fn clone_to_uninit(&self, dest: *mut u8)

impl<T> From<T> for T

fn from(t: T) -> T

impl<T, U> Into<U> for Twhere U: From<T>,

fn into(self) -> U

impl<T> ToOwned for Twhere T: Clone,

type Owned = T

fn to_owned(&self) -> T

fn clone_into(&self, target: &mut T)

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

type Error = Infallible

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

type Error = <U as TryFrom<T>>::Error

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Struct PairingHeap

impl<T, C, A> PairingHeap<T, C, A>
where C: Comparator<T>, A: MonoidAct<Key = T, Act: PartialEq>,

impl<T, A> PairingHeap<T, Less, A>
where T: Ord, A: MonoidAct<Key = T, Act: PartialEq>,

impl<T: Clone, C: Clone, A> Clone for PairingHeap<T, C, A>
where A: MonoidAct<Key = T, Act: PartialEq> + Clone,

impl<T, C, A> Debug for PairingHeap<T, C, A>
where T: Debug, C: Debug + Comparator<T>, A: MonoidAct<Key = T, Act: PartialEq + Debug>,

impl<T, C, A> Default for PairingHeap<T, C, A>
where C: Comparator<T> + Default, A: MonoidAct<Key = T, Act: PartialEq>,

impl<T, C, A> Extend<T> for PairingHeap<T, C, A>
where C: Comparator<T>, A: MonoidAct<Key = T, Act: PartialEq>,

impl<T, C, A> FromIterator<T> for PairingHeap<T, C, A>
where C: Comparator<T> + Default, A: MonoidAct<Key = T, Act: PartialEq>,

impl<T, C, A> IntoIterator for PairingHeap<T, C, A>
where C: Comparator<T>, A: MonoidAct<Key = T, Act: PartialEq>,

impl<T, C, A> Freeze for PairingHeap<T, C, A>
where C: Freeze,

impl<T, C, A> RefUnwindSafe for PairingHeap<T, C, A>
where C: RefUnwindSafe, T: RefUnwindSafe, <A as MonoidAct>::Act: RefUnwindSafe,

impl<T, C, A> Send for PairingHeap<T, C, A>
where C: Send, T: Send, <A as MonoidAct>::Act: Send,

impl<T, C, A> Sync for PairingHeap<T, C, A>
where C: Sync, T: Sync, <A as MonoidAct>::Act: Sync,

impl<T, C, A> Unpin for PairingHeap<T, C, A>
where C: Unpin,

impl<T, C, A> UnwindSafe for PairingHeap<T, C, A>
where C: UnwindSafe, T: UnwindSafe, <A as MonoidAct>::Act: UnwindSafe,

impl<T> Any for T
where T: 'static + ?Sized,

impl<T> Borrow<T> for T
where T: ?Sized,

impl<T> BorrowMut<T> for T
where T: ?Sized,

impl<T> CloneToUninit for T
where T: Clone,

impl<T, U> Into<U> for T
where U: From<T>,

impl<T> ToOwned for T
where T: Clone,

impl<T, U> TryFrom<U> for T
where U: Into<T>,

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,