1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
use super::PriorityQueue;
pub struct BinaryHeap<T: PartialOrd> {
heap: Vec<T>,
}
impl<T: PartialOrd> PriorityQueue<T> for BinaryHeap<T> {
fn with_capacity(sz: usize) -> Self {
Self {
heap: Vec::with_capacity(sz),
}
}
fn insert(&mut self, el: T) {
self.heap.push(el);
self.swim(self.heap.len() - 1);
}
fn contains(&self, el: &T) -> bool {
self.heap.contains(el)
}
fn remove(&mut self, el: &T) {
if let Some(idx) = self.heap.iter().position(|x| x == el) {
self.remove_at(idx);
}
}
fn poll(&mut self) -> Option<T> {
self.remove_at(0)
}
}
impl<T: PartialOrd> BinaryHeap<T> {
pub fn swap(&mut self, i: usize, j: usize) {
self.heap.swap(i, j);
}
fn remove_at(&mut self, i: usize) -> Option<T> {
let end = self.heap.len() - 1;
self.heap.swap(i, end);
let removed = self.heap.pop();
let i_ = self.sink(i);
if i_ == i {
self.swim(i);
}
removed
}
fn swim(&mut self, mut k: usize) -> usize {
let mut parent = (k.saturating_sub(1)) / 2;
while k > 0 && self.heap[k] < self.heap[parent] {
self.heap.swap(parent, k);
k = parent;
parent = (k.saturating_sub(1)) / 2;
}
k
}
fn sink(&mut self, mut k: usize) -> usize {
let heap_size = self.heap.len();
loop {
let left = 2 * k + 1;
let right = 2 * k + 2;
let smallest = if right < heap_size && self.heap[right] < self.heap[left] {
right
} else {
left
};
if left >= heap_size || self.heap[k] < self.heap[smallest] {
break;
}
self.heap.swap(smallest, k);
k = smallest;
}
k
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_priority_queue_binary_heap() {
let mut pq = BinaryHeap::with_capacity(8);
pq.insert(5);
pq.insert(7);
pq.insert(3);
pq.insert(8);
pq.insert(2);
pq.insert(1);
assert_eq!(pq.poll().unwrap(), 1);
pq.remove(&2);
assert_eq!(pq.poll().unwrap(), 3);
}
}