Skip to main content

PairingHeap

competitive::data_structure::pairing_heap

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 215)
214    fn default() -> Self {
215        Self::with_comparator(C::default())
216    }
Source

pub fn len(&self) -> usize

Examples found in repository?
crates/competitive/src/data_structure/pairing_heap.rs (line 357)
356    fn size_hint(&self) -> (usize, Option<usize>) {
357        let len = self.heap.len();
358        (len, Some(len))
359    }
360}
361
362impl<T, C, A> ExactSizeIterator for IntoIter<T, C, A>
363where
364    C: Comparator<T>,
365    A: MonoidAct<Key = T, Act: PartialEq>,
366{
367    fn len(&self) -> usize {
368        self.heap.len()
369    }
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 251)
249    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
250        for value in iter {
251            self.push(value);
252        }
253    }
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 = None;
185        while let Some(mut first) = head {
186            first.propagate();
187            let next = first.next_sibling.take();
188            let mut pair = if let Some(mut second) = next {
189                second.propagate();
190                head = second.next_sibling.take();
191                self.merge_option(Some(first), Some(second)).unwrap()
192            } else {
193                head = None;
194                first
195            };
196            pair.next_sibling = pairs;
197            pairs = Some(pair);
198        }
199
200        let mut result = None;
201        while let Some(mut node) = pairs {
202            pairs = node.next_sibling.take();
203            result = self.merge_option(Some(node), result);
204        }
205        result
206    }
207}
208
209impl<T, C, A> Default for PairingHeap<T, C, A>
210where
211    C: Comparator<T> + Default,
212    A: MonoidAct<Key = T, Act: PartialEq>,
213{
214    fn default() -> Self {
215        Self::with_comparator(C::default())
216    }
217}
218
219impl<T, A> PairingHeap<T, Less, A>
220where
221    T: Ord,
222    A: MonoidAct<Key = T, Act: PartialEq>,
223{
224    pub fn new() -> Self {
225        Self::default()
226    }
227}
228
229impl<T, C, A> Debug for PairingHeap<T, C, A>
230where
231    T: Debug,
232    C: Debug + Comparator<T>,
233    A: MonoidAct<Key = T, Act: PartialEq + Debug>,
234{
235    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
236        f.debug_struct("PairingHeap")
237            .field("len", &self.len)
238            .field("root", &self.root)
239            .field("cmp", &self.cmp)
240            .finish()
241    }
242}
243
244impl<T, C, A> Extend<T> for PairingHeap<T, C, A>
245where
246    C: Comparator<T>,
247    A: MonoidAct<Key = T, Act: PartialEq>,
248{
249    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
250        for value in iter {
251            self.push(value);
252        }
253    }
254}
255
256impl<T, C, A> FromIterator<T> for PairingHeap<T, C, A>
257where
258    C: Comparator<T> + Default,
259    A: MonoidAct<Key = T, Act: PartialEq>,
260{
261    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
262        let mut heap = Self::default();
263        heap.extend(iter);
264        heap
265    }
266}
267
268pub struct PeekMut<'a, T, C = Less, A = EmptyAct<T>>
269where
270    C: Comparator<T>,
271    A: MonoidAct<Key = T, Act: PartialEq>,
272{
273    heap: &'a mut PairingHeap<T, C, A>,
274    node: Option<Box<Node<T, A>>>,
275}
276
277impl<'a, T, C, A> PeekMut<'a, T, C, A>
278where
279    C: Comparator<T>,
280    A: MonoidAct<Key = T, Act: PartialEq>,
281{
282    pub fn pop(mut this: Self) -> T {
283        this.heap.len -= 1;
284        let node = this.node.take().expect("PeekMut already consumed");
285        let Node { value, .. } = *node;
286        value
287    }
288}
289
290impl<'a, T, C, A> Deref for PeekMut<'a, T, C, A>
291where
292    C: Comparator<T>,
293    A: MonoidAct<Key = T, Act: PartialEq>,
294{
295    type Target = T;
296
297    fn deref(&self) -> &Self::Target {
298        &self.node.as_ref().expect("PeekMut already consumed").value
299    }
300}
301
302impl<'a, T, C, A> DerefMut for PeekMut<'a, T, C, A>
303where
304    C: Comparator<T>,
305    A: MonoidAct<Key = T, Act: PartialEq>,
306{
307    fn deref_mut(&mut self) -> &mut Self::Target {
308        &mut self.node.as_mut().expect("PeekMut already consumed").value
309    }
310}
311
312impl<'a, T, C, A> Drop for PeekMut<'a, T, C, A>
313where
314    C: Comparator<T>,
315    A: MonoidAct<Key = T, Act: PartialEq>,
316{
317    fn drop(&mut self) {
318        if let Some(mut node) = self.node.take() {
319            debug_assert!(node.next_sibling.is_none());
320            let root = self.heap.root.take();
321            node.first_child = None;
322            self.heap.root = self.heap.merge_option(root, Some(node));
323        }
324    }
325}
326
327pub struct IntoIter<T, C = Less, A = EmptyAct<T>>
328where
329    C: Comparator<T>,
330    A: MonoidAct<Key = T, Act: PartialEq>,
331{
332    heap: PairingHeap<T, C, A>,
333}
334
335impl<T, C, A> IntoIter<T, C, A>
336where
337    C: Comparator<T>,
338    A: MonoidAct<Key = T, Act: PartialEq>,
339{
340    fn new(heap: PairingHeap<T, C, A>) -> Self {
341        Self { heap }
342    }
343}
344
345impl<T, C, A> Iterator for IntoIter<T, C, A>
346where
347    C: Comparator<T>,
348    A: MonoidAct<Key = T, Act: PartialEq>,
349{
350    type Item = T;
351
352    fn next(&mut self) -> Option<Self::Item> {
353        self.heap.pop()
354    }
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 = None;
185        while let Some(mut first) = head {
186            first.propagate();
187            let next = first.next_sibling.take();
188            let mut pair = if let Some(mut second) = next {
189                second.propagate();
190                head = second.next_sibling.take();
191                self.merge_option(Some(first), Some(second)).unwrap()
192            } else {
193                head = None;
194                first
195            };
196            pair.next_sibling = pairs;
197            pairs = Some(pair);
198        }
199
200        let mut result = None;
201        while let Some(mut node) = pairs {
202            pairs = node.next_sibling.take();
203            result = self.merge_option(Some(node), result);
204        }
205        result
206    }
207}
208
209impl<T, C, A> Default for PairingHeap<T, C, A>
210where
211    C: Comparator<T> + Default,
212    A: MonoidAct<Key = T, Act: PartialEq>,
213{
214    fn default() -> Self {
215        Self::with_comparator(C::default())
216    }
217}
218
219impl<T, A> PairingHeap<T, Less, A>
220where
221    T: Ord,
222    A: MonoidAct<Key = T, Act: PartialEq>,
223{
224    pub fn new() -> Self {
225        Self::default()
226    }
227}
228
229impl<T, C, A> Debug for PairingHeap<T, C, A>
230where
231    T: Debug,
232    C: Debug + Comparator<T>,
233    A: MonoidAct<Key = T, Act: PartialEq + Debug>,
234{
235    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
236        f.debug_struct("PairingHeap")
237            .field("len", &self.len)
238            .field("root", &self.root)
239            .field("cmp", &self.cmp)
240            .finish()
241    }
242}
243
244impl<T, C, A> Extend<T> for PairingHeap<T, C, A>
245where
246    C: Comparator<T>,
247    A: MonoidAct<Key = T, Act: PartialEq>,
248{
249    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
250        for value in iter {
251            self.push(value);
252        }
253    }
254}
255
256impl<T, C, A> FromIterator<T> for PairingHeap<T, C, A>
257where
258    C: Comparator<T> + Default,
259    A: MonoidAct<Key = T, Act: PartialEq>,
260{
261    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
262        let mut heap = Self::default();
263        heap.extend(iter);
264        heap
265    }
266}
267
268pub struct PeekMut<'a, T, C = Less, A = EmptyAct<T>>
269where
270    C: Comparator<T>,
271    A: MonoidAct<Key = T, Act: PartialEq>,
272{
273    heap: &'a mut PairingHeap<T, C, A>,
274    node: Option<Box<Node<T, A>>>,
275}
276
277impl<'a, T, C, A> PeekMut<'a, T, C, A>
278where
279    C: Comparator<T>,
280    A: MonoidAct<Key = T, Act: PartialEq>,
281{
282    pub fn pop(mut this: Self) -> T {
283        this.heap.len -= 1;
284        let node = this.node.take().expect("PeekMut already consumed");
285        let Node { value, .. } = *node;
286        value
287    }
288}
289
290impl<'a, T, C, A> Deref for PeekMut<'a, T, C, A>
291where
292    C: Comparator<T>,
293    A: MonoidAct<Key = T, Act: PartialEq>,
294{
295    type Target = T;
296
297    fn deref(&self) -> &Self::Target {
298        &self.node.as_ref().expect("PeekMut already consumed").value
299    }
300}
301
302impl<'a, T, C, A> DerefMut for PeekMut<'a, T, C, A>
303where
304    C: Comparator<T>,
305    A: MonoidAct<Key = T, Act: PartialEq>,
306{
307    fn deref_mut(&mut self) -> &mut Self::Target {
308        &mut self.node.as_mut().expect("PeekMut already consumed").value
309    }
310}
311
312impl<'a, T, C, A> Drop for PeekMut<'a, T, C, A>
313where
314    C: Comparator<T>,
315    A: MonoidAct<Key = T, Act: PartialEq>,
316{
317    fn drop(&mut self) {
318        if let Some(mut node) = self.node.take() {
319            debug_assert!(node.next_sibling.is_none());
320            let root = self.heap.root.take();
321            node.first_child = None;
322            self.heap.root = self.heap.merge_option(root, Some(node));
323        }
324    }
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) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · 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: T)

🔬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 Option<Box<Node<T, A>>>: Freeze, C: Freeze,

§

impl<T, C, A> RefUnwindSafe for PairingHeap<T, C, A>
where Option<Box<Node<T, A>>>: RefUnwindSafe, C: RefUnwindSafe,

§

impl<T, C, A> Send for PairingHeap<T, C, A>
where Option<Box<Node<T, A>>>: Send, C: Send,

§

impl<T, C, A> Sync for PairingHeap<T, C, A>
where Option<Box<Node<T, A>>>: Sync, C: Sync,

§

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

§

impl<T, C, A> UnsafeUnpin for PairingHeap<T, C, A>
where Option<Box<Node<T, A>>>: UnsafeUnpin, C: UnsafeUnpin,

§

impl<T, C, A> UnwindSafe for PairingHeap<T, C, A>
where Option<Box<Node<T, A>>>: UnwindSafe, C: 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<U> 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> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

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<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

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

Source§

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

The type returned in the event of a conversion error.
Source§

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

Performs the conversion.