pqueue/
lib.rs

1#![no_std]
2mod test;
3
4extern crate alloc;
5use alloc::vec::Vec;
6
7pub struct Queue<T: PartialOrd> {
8    items: Vec<T>,
9}
10
11impl<T: PartialOrd> Queue<T> {
12    pub fn new() -> Queue<T> {
13        Queue { items: Vec::new() }
14    }
15    pub fn push(self: &mut Queue<T>, item: T) {
16        self.items.push(item);
17        let mut i = self.items.len() - 1;
18        while i != 0 {
19            let parent = (i - 1) / 2;
20            if !(self.items[parent] > self.items[i]) {
21                break;
22            }
23            self.items.swap(parent, i);
24            i = parent;
25
26        }
27    }
28    pub fn len(self: &Queue<T>) -> usize {
29        self.items.len()
30    }
31    pub fn peek(self: &Queue<T>) -> Option<&T> {
32        if self.items.len() == 0 {
33            None
34        } else {
35            Some(&self.items[0])
36        }
37    }
38    pub fn pop(self: &mut Queue<T>) -> Option<T> {
39        if self.items.len() == 0 {
40            return None;
41        }
42        let n = self.items.swap_remove(0);
43        let mut i = 0;
44        loop {
45            let mut smallest = i;
46            let left = i * 2 + 1;
47            let right = i * 2 + 2;
48            if left < self.items.len() && self.items[left] <= self.items[smallest] {
49                smallest = left
50            }
51            if right < self.items.len() && self.items[right] <= self.items[smallest] {
52                smallest = right
53            }
54            if smallest == i {
55                break;
56            }
57            self.items.swap(smallest, i);
58            i = smallest;
59        }
60        Some(n)
61    }
62}
pqueue/lib.rs

pqueue/
lib.rs
