pairing_heap/
lib.rs

1//! A priority queue based on a [pairing heap].
2//!
3//! See [`PairingHeap`](struct.PairingHeap.html) for details.
4//!
5//! [pairing heap]: https://en.wikipedia.org/wiki/Pairing_heap
6
7#![deny(missing_docs)]
8
9use std::fmt::{self, Debug};
10use std::{mem, slice};
11
12#[derive(Clone)]
13struct Node<T> {
14    item: T,
15    children: Vec<Node<T>>,
16}
17
18impl<T> Node<T> {
19    fn merge(&mut self, mut other: Self) where T: Ord {
20        if self.item < other.item {
21            mem::swap(self, &mut other);
22        }
23
24        self.children.push(other);
25    }
26
27    fn reduce(nodes: Vec<Self>) -> Option<Self> where T: Ord {
28        fn unwrap<T>(option: Option<T>) -> T {
29            match option {
30                None => if cfg!(debug) { panic!() } else { unreachable!() },
31                Some(t) => t,
32            }
33        }
34
35        let mut nodes = nodes.into_iter();
36
37        nodes.next().map(|mut root| {
38            if nodes.len() % 2 == 1 {
39                root.merge(unwrap(nodes.next()));
40            }
41
42            while let Some(mut node) = nodes.next() {
43                node.merge(unwrap(nodes.next()));
44                root.merge(node);
45            }
46
47            root
48        })
49    }
50
51    fn replace_item(&mut self, mut item: T) -> T where T: Ord {
52        mem::swap(&mut item, &mut self.item);
53        let mut node = self;
54
55        loop {
56            let tmp = node;
57            let mut it = tmp.children.iter_mut();
58
59            match it.next() {
60                None => return item,
61                Some(mut max) => {
62                    for child in it {
63                        if child.item > max.item {
64                            max = child;
65                        }
66                    }
67
68                    if tmp.item > max.item { return item; }
69                    mem::swap(&mut tmp.item, &mut max.item);
70                    node = max;
71                }
72            }
73        }
74    }
75}
76
77/// An iterator that drains a `PairingHeap`, yielding its items in arbitrary order.
78///
79/// Acquire through [`PairingHeap::drain`](struct.PairingHeap.html#method.drain).
80pub struct Drain<'a, T: 'a + Ord> {
81    heap: &'a mut PairingHeap<T>,
82}
83
84impl<'a, T: Ord> Drop for Drain<'a, T> {
85    fn drop(&mut self) {
86        self.heap.clear();
87    }
88}
89
90impl<'a, T: Ord> Iterator for Drain<'a, T> {
91    type Item = T;
92
93    fn next(&mut self) -> Option<T> {
94        self.heap.pop()
95    }
96
97    fn size_hint(&self) -> (usize, Option<usize>) {
98        (self.heap.len, Some(self.heap.len))
99    }
100}
101
102impl<'a, T: Ord> ExactSizeIterator for Drain<'a, T> {
103    fn len(&self) -> usize {
104        self.heap.len
105    }
106}
107
108/// An iterator that yields the items in a `PairingHeap` in arbitrary order.
109///
110/// Acquire through [`IntoIterator::into_iter`](struct.PairingHeap.html#method.into_iter).
111pub struct IntoIter<T: Ord> {
112    heap: PairingHeap<T>,
113}
114
115impl<T: Ord> Iterator for IntoIter<T> {
116    type Item = T;
117
118    fn next(&mut self) -> Option<T> {
119        self.heap.pop()
120    }
121
122    fn size_hint(&self) -> (usize, Option<usize>) {
123        (self.heap.len, Some(self.heap.len))
124    }
125}
126
127impl<T: Ord> ExactSizeIterator for IntoIter<T> {
128    fn len(&self) -> usize {
129        self.heap.len
130    }
131}
132
133/// An iterator that yields references to the items in a `PairingHeap` in arbitrary order.
134///
135/// Acquire through [`PairingHeap::iter`](struct.PairingHeap.html#method.iter).
136pub struct Iter<'a, T: 'a + Ord> {
137    iters: Vec<slice::Iter<'a, Node<T>>>,
138    len: usize,
139}
140
141impl<'a, T: Ord> Clone for Iter<'a, T> {
142    fn clone(&self) -> Self {
143        Iter { iters: self.iters.clone(), len: self.len }
144    }
145}
146
147impl<'a, T: Ord> Iterator for Iter<'a, T> {
148    type Item = &'a T;
149
150    fn next(&mut self) -> Option<&'a T> {
151        loop {
152            let node = match self.iters.last_mut() {
153                None => return None,
154                Some(iter) => iter.next(),
155            };
156
157            if let Some(node) = node {
158                self.iters.push(node.children.iter());
159                self.len -= 1;
160                return Some(&node.item);
161            }
162
163            self.iters.pop();
164        }
165    }
166
167    fn size_hint(&self) -> (usize, Option<usize>) {
168        (self.len, Some(self.len))
169    }
170}
171
172impl<'a, T: Ord> ExactSizeIterator for Iter<'a, T> {
173    fn len(&self) -> usize {
174        self.len
175    }
176}
177
178/// A priority queue based on a pairing heap.
179///
180/// Like [`BinaryHeap`], `PairingHeap` is an implementation of a priority queue. Unlike
181/// `BinaryHeap`, `PairingHeap` provides an `append` method whose runtime is asymptotically
182/// optimal, at the cost of greater memory usage, slower iteration, and poor cache locality.
183///
184/// # Time Complexity
185///
186/// | Operation                      | Time Complexity        |
187/// |--------------------------------|------------------------|
188/// | [`append`](#method.append)     | `O(1)`                 |
189/// | [`peek`](#method.peek)         | `O(1)`                 |
190/// | [`pop`](#method.pop)           | `O(log n)` (amortized) |
191/// | [`push`](#method.push)         | `O(1) `                |
192/// | [`push_pop`](#method.push_pop) | `O(log n)` (amortized) |
193/// | [`replace`](#method.replace)   | `O(log n)` (amortized) |
194///
195/// [`BinaryHeap`]: https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html
196#[derive(Clone)]
197pub struct PairingHeap<T: Ord> {
198    root: Option<Node<T>>,
199    len: usize,
200}
201
202impl<T: Ord> PairingHeap<T> {
203    /// Returns a new heap.
204    pub fn new() -> Self {
205        PairingHeap { root: None, len: 0 }
206    }
207
208    /// Checks if the heap is empty.
209    pub fn is_empty(&self) -> bool {
210        self.root.is_none()
211    }
212
213    /// Returns the number of items in the heap.
214    pub fn len(&self) -> usize {
215        self.len
216    }
217
218    /// Returns an iterator that yields references to the items in the heap in arbitrary order.
219    pub fn iter(&self) -> Iter<T> {
220        Iter {
221            iters: self.root.as_ref()
222                .map(|root| unsafe { slice::from_raw_parts(root, 1) }.iter())
223                .into_iter()
224                .collect(),
225            len: self.len,
226        }
227    }
228
229    /// Returns a reference to the greatest item in the heap.
230    ///
231    /// Returns `None` if the heap is empty.
232    pub fn peek(&self) -> Option<&T> {
233        self.root.as_ref().map(|root| &root.item)
234    }
235
236    /// Pushes the given item onto the heap.
237    pub fn push(&mut self, item: T) {
238        self.len += 1;
239        let node = Node { item: item, children: vec![] };
240
241        match self.root {
242            None => self.root = Some(node),
243            Some(ref mut root) => root.merge(node),
244        }
245    }
246
247    /// Moves the given heap's items into the heap, leaving the given heap empty.
248    ///
249    /// This is equivalent to, but likely to be faster than, the following:
250    ///
251    /// ```
252    /// # let mut heap = pairing_heap::PairingHeap::<i32>::new();
253    /// # let mut heap2 = pairing_heap::PairingHeap::new();
254    /// heap.extend(heap2.drain());
255    /// ```
256    pub fn append(&mut self, other: &mut Self) {
257        match self.root {
258            None => mem::swap(self, other),
259            Some(ref mut root) => if let Some(other_root) = other.root.take() {
260                root.merge(other_root);
261                self.len += mem::replace(&mut other.len, 0);
262            },
263        }
264    }
265
266    /// Pushes the given item onto the heap, then removes the greatest item in the heap and returns
267    /// it.
268    ///
269    /// This method is equivalent to, but likely faster than, the following:
270    ///
271    /// ```
272    /// # let mut heap = pairing_heap::PairingHeap::new();
273    /// # let item = 0;
274    /// heap.push(item);
275    /// let max = heap.pop().unwrap();
276    /// ```
277    pub fn push_pop(&mut self, item: T) -> T {
278        match self.root {
279            Some(ref mut root) if item < root.item => root.replace_item(item),
280            _ => item,
281        }
282    }
283
284    /// Removes the greatest item in the heap, then pushes the given item onto the heap.
285    ///
286    /// Returns the item that was removed, or `None` if the heap was empty.
287    ///
288    /// This method is equivalent to, but likely faster than, the following:
289    ///
290    /// ```
291    /// # let mut heap = pairing_heap::PairingHeap::new();
292    /// # let item = 0;
293    /// let max = heap.pop();
294    /// heap.push(item);
295    /// ```
296    pub fn replace(&mut self, item: T) -> Option<T> {
297        match self.root {
298            None => { self.push(item); None }
299            Some(ref mut root) => Some(root.replace_item(item)),
300        }
301    }
302
303    /// Removes the greatest item in the heap and returns it.
304    ///
305    /// Returns `None` if the heap was empty.
306    ///
307    /// If a call to this method is immediately preceded by a call to [`push`], consider using
308    /// [`push_pop`] instead. If a call to this method is immediately followed by a call to
309    /// [`push`], consider using [`replace`] instead.
310    ///
311    /// [`push`]: #method.push
312    /// [`push_pop`]: #method.push_pop
313    /// [`replace`]: #method.replace
314    pub fn pop(&mut self) -> Option<T> {
315        self.root.take().map(|Node { item, children }| {
316            self.len -= 1;
317            self.root = Node::reduce(children);
318            item
319        })
320    }
321
322    /// Removes all items from the heap.
323    pub fn clear(&mut self) {
324        *self = Self::new();
325    }
326
327    /// Removes all items from the heap and returns an iterator that yields them in arbitrary
328    /// order.
329    ///
330    /// All items are removed even if the iterator is not exhausted. However, the behavior of
331    /// this method is unspecified if the iterator is leaked (e.g. via [`mem::forget`]).
332    ///
333    /// [`mem::forget`]: https://doc.rust-lang.org/std/mem/fn.forget.html
334    pub fn drain(&mut self) -> Drain<T> {
335        Drain { heap: self }
336    }
337}
338
339impl<T: Ord + Debug> Debug for PairingHeap<T> {
340    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
341        f.debug_list().entries(self).finish()
342    }
343}
344
345impl<T: Ord> Default for PairingHeap<T> {
346    fn default() -> Self {
347        Self::new()
348    }
349}
350
351impl<T: Ord> Extend<T> for PairingHeap<T> {
352    fn extend<I: IntoIterator<Item = T>>(&mut self, items: I) {
353        for item in items { self.push(item); }
354    }
355}
356
357impl<T: Ord> std::iter::FromIterator<T> for PairingHeap<T> {
358    fn from_iter<I: IntoIterator<Item = T>>(items: I) -> Self {
359        let mut heap = Self::new();
360        heap.extend(items);
361        heap
362    }
363}
364
365impl<T: Ord> IntoIterator for PairingHeap<T> {
366    type Item = T;
367    type IntoIter = IntoIter<T>;
368
369    fn into_iter(self) -> IntoIter<T> {
370        IntoIter { heap: self }
371    }
372}
373
374impl<'a, T: Ord> IntoIterator for &'a PairingHeap<T> {
375    type Item = &'a T;
376    type IntoIter = Iter<'a, T>;
377
378    fn into_iter(self) -> Iter<'a, T> {
379        self.iter()
380    }
381}
pairing_heap/lib.rs

pairing_heap/
lib.rs
