competitive_programming_rs/data_structure/
fibonacci_heap.rs1pub mod fibonacci_heap {
2 use std::collections::{HashMap, LinkedList};
3
4 #[derive(Debug)]
5 struct Node<T> {
6 value: T,
7 children: Vec<Node<T>>,
8 }
9
10 #[derive(Debug)]
11 pub struct FibonacciHeap<T> {
12 nodes: LinkedList<Node<T>>,
13 size: usize,
14 }
15
16 impl<T> FibonacciHeap<T> {
17 pub fn new() -> Self {
18 Self {
19 nodes: LinkedList::new(),
20 size: 0,
21 }
22 }
23 }
24
25 impl<T> FibonacciHeap<T> {
26 pub fn len(&self) -> usize {
27 self.size
28 }
29 }
30
31 impl<T: PartialOrd> FibonacciHeap<T> {
32 pub fn push(&mut self, value: T) {
33 let node = Node {
34 value,
35 children: vec![],
36 };
37 self.push_node(node);
38 self.size += 1;
39 }
40
41 fn push_node(&mut self, node: Node<T>) {
42 match self.nodes.iter().next() {
43 Some(first) => {
44 if first.value > node.value {
45 self.nodes.push_front(node);
46 } else {
47 self.nodes.push_back(node);
48 }
49 }
50 None => {
51 self.nodes.push_back(node);
52 }
53 }
54 }
55
56 pub fn pop(&mut self) -> Option<T> {
57 let min = match self.nodes.pop_front() {
58 Some(min) => min,
59 None => {
60 assert_eq!(self.size, 0);
61 return None;
62 }
63 };
64
65 let mut node_by_deg = HashMap::new();
66 let popped = min.value;
67 for node in min.children {
68 consolidate(node, &mut node_by_deg);
69 }
70
71 while let Some(node) = self.nodes.pop_front() {
72 consolidate(node, &mut node_by_deg);
73 }
74 assert!(self.nodes.is_empty());
75 for (_, node) in node_by_deg {
76 self.push_node(node);
77 }
78 assert!(self.size > 0);
79 self.size -= 1;
80 Some(popped)
81 }
82
83 pub fn peek(&self) -> Option<&T> {
84 self.nodes.iter().next().map(|node| &node.value)
85 }
86
87 pub fn merge(self, other: Self) -> Self {
88 let FibonacciHeap {
89 nodes: mut a_nodes,
90 size: a_size,
91 } = self;
92 let FibonacciHeap {
93 nodes: mut b_nodes,
94 size: b_size,
95 } = other;
96
97 let size = a_size + b_size;
98
99 match (a_nodes.pop_front(), b_nodes.pop_front()) {
100 (Some(a), Some(b)) => {
101 let (small, large) = if a.value < b.value { (a, b) } else { (b, a) };
102 a_nodes.append(&mut b_nodes);
103 a_nodes.push_front(large);
104 a_nodes.push_front(small);
105 Self {
106 nodes: a_nodes,
107 size,
108 }
109 }
110 (Some(a), None) => {
111 assert_eq!(a_size, size);
112 a_nodes.push_front(a);
113 Self {
114 nodes: a_nodes,
115 size,
116 }
117 }
118 (None, Some(b)) => {
119 assert_eq!(b_size, size);
120 b_nodes.push_front(b);
121 Self {
122 nodes: b_nodes,
123 size,
124 }
125 }
126 (None, None) => {
127 assert_eq!(size, 0);
128 Self {
129 nodes: LinkedList::new(),
130 size,
131 }
132 }
133 }
134 }
135 }
136
137 fn consolidate<T: PartialOrd>(node: Node<T>, node_by_deg: &mut HashMap<usize, Node<T>>) {
138 let degree = node.children.len();
139 if let Some(same_degree_node) = node_by_deg.remove(°ree) {
140 assert_eq!(same_degree_node.children.len(), degree);
141 let (mut small, large) = if same_degree_node.value < node.value {
142 (same_degree_node, node)
143 } else {
144 (node, same_degree_node)
145 };
146 small.children.push(large);
147 consolidate(small, node_by_deg);
148 } else {
149 node_by_deg.insert(degree, node);
150 }
151 }
152}
153
154#[cfg(test)]
155mod tests {
156 use super::fibonacci_heap::*;
157 use rand::prelude::*;
158 use std::cmp::Reverse;
159 use std::collections::BinaryHeap;
160
161 #[test]
162 fn test_fibonacci_heap() {
163 let mut min_heap = FibonacciHeap::new();
164
165 assert_eq!(min_heap.len(), 0);
166 min_heap.push(1);
167 assert_eq!(min_heap.len(), 1);
168 assert_eq!(min_heap.pop(), Some(1));
169 assert_eq!(min_heap.len(), 0);
170
171 min_heap.push(1);
172 assert_eq!(min_heap.len(), 1);
173 min_heap.push(2);
174 assert_eq!(min_heap.len(), 2);
175 min_heap.push(3);
176 assert_eq!(min_heap.len(), 3);
177
178 assert_eq!(min_heap.pop(), Some(1));
179 assert_eq!(min_heap.len(), 2);
180 assert_eq!(min_heap.pop(), Some(2));
181 assert_eq!(min_heap.len(), 1);
182 assert_eq!(min_heap.pop(), Some(3));
183 assert_eq!(min_heap.len(), 0);
184
185 min_heap.push(3);
186 min_heap.push(2);
187 min_heap.push(1);
188 assert_eq!(min_heap.pop(), Some(1));
189 assert_eq!(min_heap.pop(), Some(2));
190 assert_eq!(min_heap.pop(), Some(3));
191 }
192
193 #[test]
194 fn compare_to_binary_heap() {
195 let mut rng = thread_rng();
196 let mut max_heap = FibonacciHeap::new();
197 let mut binary_heap = BinaryHeap::new();
198
199 for _ in 0..2000 {
200 let x = rng.gen::<usize>() % 10;
201
202 if x == 0 {
203 assert_eq!(max_heap.pop().map(|x: Reverse<u8>| x.0), binary_heap.pop());
204 } else {
205 let v = rng.gen::<u8>();
206 max_heap.push(Reverse(v));
207 binary_heap.push(v);
208 }
209
210 assert_eq!(max_heap.len(), binary_heap.len());
211 }
212 }
213
214 #[test]
215 fn merge_heaps() {
216 let mut rng = thread_rng();
217 let mut check = vec![];
218
219 let mut a_heap = FibonacciHeap::new();
220 for _ in 0..2000 {
221 let x = rng.gen_range(0, 100);
222 a_heap.push(x);
223 check.push(x);
224 }
225 let mut b_heap = FibonacciHeap::new();
226 for _ in 0..2000 {
227 let x = rng.gen_range(0, 100);
228 b_heap.push(x);
229 check.push(x);
230 }
231 a_heap = a_heap.merge(b_heap);
232
233 assert_eq!(a_heap.len(), check.len());
234 check.sort();
235 check.reverse();
236 while let Some(v) = check.pop() {
237 let head = a_heap.pop().unwrap();
238 assert_eq!(head, v);
239 }
240 }
241}