competitive_programming_lib/DataStructures/
binary_heap.rs

1pub struct MaxHeap {
2    data: Vec<i32>,
3}
4
5impl MaxHeap {
6    pub fn new() -> Self {
7        MaxHeap { data: Vec::new() }
8    }
9
10    pub fn push(&mut self, value: i32) {
11        self.data.push(value);
12        self.heapify_up(self.data.len() - 1);
13    }
14
15    pub fn pop(&mut self) -> Option<i32> {
16        if self.data.is_empty() {
17            return None;
18        }
19        let root = self.data.swap_remove(0);
20        self.heapify_down(0);
21        Some(root)
22    }
23
24    fn heapify_up(&mut self, mut index: usize) {
25        while index > 0 {
26            let parent = (index - 1) / 2;
27            if self.data[index] > self.data[parent] {
28                self.data.swap(index, parent);
29                index = parent;
30            } else {
31                break;
32            }
33        }
34    }
35
36    fn heapify_down(&mut self, mut index: usize) {
37        let len = self.data.len();
38        loop {
39            let left = 2 * index + 1;
40            let right = 2 * index + 2;
41            let mut largest = index;
42
43            if left < len && self.data[left] > self.data[largest] {
44                largest = left;
45            }
46
47            if right < len && self.data[right] > self.data[largest] {
48                largest = right;
49            }
50
51            if largest == index {
52                break;
53            }
54
55            self.data.swap(index, largest);
56            index = largest;
57        }
58    }
59}