priority_queue_rs/
lib.rs

1struct PriorityQueueNode<T> where T: Sized {
2    pub priority: u32,
3    pub value: Option<T>,
4}
5
6impl<T> PriorityQueueNode<T> {
7    pub fn new(priority: u32, value: T) -> PriorityQueueNode<T> {
8        PriorityQueueNode {
9            priority,
10            value: Some(value),
11        }
12    }
13}
14
15impl<T> Drop for PriorityQueueNode<T> {
16    fn drop(&mut self) {
17        // println!("value :{} is destory", self.priority);
18    }
19}
20
21
22struct PriorityQueue<T> where T: Sized {
23    pub nodes: Vec<Option<Box<PriorityQueueNode<T>>>>,
24}
25
26impl<T> PriorityQueue<T> {
27    pub fn new() -> PriorityQueue<T> {
28        PriorityQueue {
29            nodes: Vec::with_capacity(128),
30        }
31    }
32
33    pub fn pop(&mut self) -> Option<T> {
34        if self.nodes.len() < 1 {
35            return None;
36        }
37        let top = self.nodes[0].take();
38        let mut max_pos = 0;
39        let mut cur_pos = 0;
40
41        let bottom_node = self.nodes.pop().unwrap();
42        if self.nodes.len() < 1 {
43            return top.unwrap().value.take();
44        }
45
46        self.nodes[max_pos] = bottom_node;
47        let priority = self.nodes[max_pos].as_ref().unwrap().priority;
48        let queue_len = self.nodes.len();
49
50        loop {
51            let left_child_pos = max_pos * 2 + 1;
52            let right_child_pos = max_pos * 2 + 2;
53
54            if left_child_pos < queue_len && right_child_pos < queue_len {
55                let left_child_priority = self.nodes[left_child_pos].as_ref().unwrap().priority;
56                let right_child_priority = self.nodes[right_child_pos].as_ref().unwrap().priority;
57                if left_child_priority > right_child_priority {
58                    max_pos = left_child_pos;
59                } else {
60                    max_pos = right_child_pos;
61                }
62            } else if left_child_pos < queue_len {
63                let left_child_priority = self.nodes[left_child_pos].as_ref().unwrap().priority;
64                if left_child_priority > priority {
65                    max_pos = left_child_pos;
66                }
67            } else if right_child_pos < queue_len {
68                let right_child_priority = self.nodes[right_child_pos].as_ref().unwrap().priority;
69                if right_child_priority > priority {
70                    max_pos = right_child_pos;
71                }
72            }
73            if max_pos < 1 || cur_pos == max_pos {
74                break;
75            }
76            if priority > self.nodes[max_pos].as_ref().unwrap().priority {
77                break;
78            }
79
80            let cur_node = self.nodes[cur_pos].take();
81            let max_node = self.nodes[max_pos].take();
82            self.nodes[max_pos] = cur_node;
83            self.nodes[cur_pos] = max_node;
84            cur_pos = max_pos;
85        }
86        return top.unwrap().value.take();
87    }
88
89    pub fn peek(&mut self) -> Option<&mut T> {
90        if self.nodes.len() < 1 {
91            return None;
92        }
93        return self.nodes[0].as_mut().unwrap().value.as_mut();
94    }
95
96    pub fn push(&mut self, priority: u32, value: T) {
97        if self.nodes.len() < 1 {
98            self.nodes.push(Some(Box::new(PriorityQueueNode::new(priority, value))));
99            return;
100        }
101        let mut compare_pos = (self.nodes.len() - 1) / 2;
102        let new_node = PriorityQueueNode::new(priority, value);
103        self.nodes.push(Some(Box::new(new_node)));
104        let mut new_node_pos = self.nodes.len() - 1;
105        loop {
106            if priority > self.nodes[compare_pos].as_ref().unwrap().priority {
107                let new_node = self.nodes[new_node_pos].take();
108                self.nodes[new_node_pos] = self.nodes[compare_pos].take();
109                self.nodes[compare_pos] = new_node;
110            } else {
111                break;
112            }
113            if compare_pos < 1 {
114                break;
115            }
116            new_node_pos = compare_pos;
117            compare_pos = (compare_pos - 1) / 2;
118        }
119    }
120}
121
122#[cfg(test)]
123mod test {
124    use super::*;
125
126    #[test]
127    fn main() {
128        let mut queue = PriorityQueue::new();
129        for priority in 10..10000 {
130            queue.push(priority, String::from(format!("HelloWorld{}", priority)));
131        }
132
133        if let Some(t) = queue.peek() {
134            println!("peek {}", t);
135        }
136
137        for priority in 0..10 {
138            let value = queue.pop();
139            if let Some(t) = value {
140                println!("pop {}", t);
141            }
142        }
143
144        if let Some(t) = queue.peek() {
145            println!("peek {}", t);
146        }
147    }
148}
priority_queue_rs/lib.rs

priority_queue_rs/
lib.rs
