rudac/heap/
minmax.rs

1/// A min-max heap provides constant time retrieval and logarithmic time removal of both the min and max elements in it.
2/// This makes the min-max heap a very useful data structure to implement a double-ended priority queue
3///
4/// # Examples
5/// ```
6/// use rudac::heap::MinMax;
7///
8/// // you can either initialize an empty heap with zero initial capacity
9/// let empty_heap: MinMax<usize> = MinMax::init();
10///
11/// // or an empty heap with initial capacity to reduce relocation
12/// let with_cap_heap: MinMax<usize> = MinMax::with_capacity(128);
13///
14/// // or construct a min-max heap from an existing vector
15/// let built_heap = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);
16///
17/// // inspect max or min values
18/// assert_eq!(*built_heap.peek_min().unwrap(), 1);
19/// assert_eq!(*built_heap.peek_max().unwrap(), 11);
20/// ```
21pub struct MinMax<T: std::cmp::Ord> {
22    tree: Vec<T>,
23}
24
25impl<T: std::cmp::Ord> MinMax<T> {
26    /// Initializes a heap with zero capacity
27    ///
28    /// # Examples
29    /// ```
30    /// use rudac::heap::MinMax;
31    ///
32    /// let minmax: MinMax<usize> = MinMax::init();
33    ///
34    /// assert_eq!(minmax.capacity(), 0);
35    /// ```
36    pub fn init() -> MinMax<T> {
37        MinMax { tree: Vec::new() }
38    }
39
40    /// Initializes a heap with specified `capacity`
41    ///
42    /// # Examples
43    /// ```
44    /// use rudac::heap::MinMax;
45    ///
46    /// let minmax: MinMax<usize> = MinMax::with_capacity(128);
47    ///
48    /// assert_eq!(minmax.capacity(), 128);
49    /// ```
50    pub fn with_capacity(capacity: usize) -> MinMax<T> {
51        MinMax {
52            tree: Vec::with_capacity(capacity),
53        }
54    }
55
56    /// Builds a heap using a bottom-up approach.
57    /// * Complexity: O(n)
58    ///
59    /// # Arguments
60    /// * `vector`: vector to build the heap from
61    ///
62    /// # Examples
63    /// ```
64    /// use rudac::heap::MinMax;
65    ///
66    /// let minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);
67    ///
68    /// assert_eq!(*minmax.peek_min().unwrap(), 1);
69    /// assert_eq!(*minmax.peek_max().unwrap(), 11);
70    /// ```
71    pub fn build_heap(vector: Vec<T>) -> MinMax<T> {
72        let mut minmax_heap = MinMax { tree: vector };
73
74        // to achieve O(n) complexity, method must traverse only inner nodes and escape leaves
75        // thus it should iterate over from last inner node till the root
76        // half of the nodes are leaves thus size / 2 shows the position of first leaf(size / 2 ... size are leaves)
77        let upper_bound = minmax_heap.size() / 2;
78
79        for i in (0..upper_bound).rev() {
80            // push down inner nodes
81            minmax_heap.push_down(i);
82        }
83
84        minmax_heap
85    }
86
87    // pushes down a node down the heap
88    // it first determines wether node is one a max level or min level
89    // then calls the appropriate method
90    fn push_down(&mut self, index: usize) {
91        if is_on_min_level(index) {
92            self.push_down_min(index);
93        } else {
94            self.push_down_max(index);
95        }
96    }
97
98    // pushes down a node that resides on a min level
99    fn push_down_min(&mut self, mut index: usize) {
100        // push down the node until heap property is restored
101        while has_child(index, self.size()) {
102            // find smallest value in children or grandchildren of the current node
103            let (smallest_index, is_grandchild) = self.smallest_child_or_grandchild(index);
104
105            // if smallest node is a grandchild of the current node, we must take care of the child of the current node
106            // on the other hand if smallest node is the direct child of the current node, just swap them
107            if is_grandchild {
108                if self.tree[smallest_index] < self.tree[index] {
109                    self.tree.swap(smallest_index, index);
110
111                    // because smallest index refers to a grandchild of current node, swapping them *may* invalidate the heap property
112                    // parent of the specified grandchild might be smaller than the current node(which is swapped)
113                    // thus after swapping we must check wether parent of the node referred by smallest index is smaller than it or not
114                    if self.tree[smallest_index] > self.tree[parent(smallest_index)] {
115                        self.tree.swap(smallest_index, parent(smallest_index));
116                    }
117                }
118            } else {
119                // just swap the parent and child
120                if self.tree[smallest_index] < self.tree[index] {
121                    self.tree.swap(index, smallest_index);
122                }
123            }
124            // iterate until heap property is restored
125            index = smallest_index;
126        }
127    }
128
129    // it's like push_down_min
130    fn push_down_max(&mut self, mut index: usize) {
131        while has_child(index, self.size()) {
132            let (greatest_index, is_grandchild) = self.greatest_child_or_grandchild(index);
133            if is_grandchild {
134                if self.tree[greatest_index] > self.tree[index] {
135                    self.tree.swap(index, greatest_index);
136
137                    if self.tree[greatest_index] < self.tree[parent(greatest_index)] {
138                        self.tree.swap(greatest_index, parent(greatest_index));
139                    }
140                }
141            } else {
142                if self.tree[greatest_index] > self.tree[index] {
143                    self.tree.swap(index, greatest_index);
144                }
145            }
146            index = greatest_index;
147        }
148    }
149
150    // finds the smallest node among children and grandchildren of the node referenced by `index`
151    // returns the index of the smallest node and also returns true if that node is a grandchild and false if it's a child
152    fn smallest_child_or_grandchild(&self, index: usize) -> (usize, bool) {
153        // check left sub tree
154        if has_left_child(index, self.size()) {
155            let left_child_index = left_child(index);
156
157            let mut smallest_index = left_child_index;
158            let mut is_grandchild = false;
159            if self.tree[left_child_index] < self.tree[smallest_index] {
160                smallest_index = left_child_index;
161                is_grandchild = false;
162            }
163
164            // check grandchildren of left sub tree
165            if has_left_child(left_child_index, self.size()) {
166                let left_grandchild_index = left_child(left_child_index);
167                if self.tree[left_grandchild_index] < self.tree[smallest_index] {
168                    smallest_index = left_grandchild_index;
169                    is_grandchild = true;
170                }
171            }
172            if has_right_child(left_child_index, self.size()) {
173                let right_grandchild_index = right_child(left_child_index);
174                if self.tree[right_grandchild_index] < self.tree[smallest_index] {
175                    smallest_index = right_grandchild_index;
176                    is_grandchild = true;
177                }
178            }
179
180            // check right sub tree
181            if has_right_child(index, self.size()) {
182                let right_child_index = right_child(index);
183                if self.tree[right_child_index] < self.tree[smallest_index] {
184                    smallest_index = right_child_index;
185                    is_grandchild = false;
186                }
187
188                // check grandchildren of right sub tree
189                if has_left_child(right_child_index, self.size()) {
190                    let left_grandchild_index = left_child(right_child_index);
191                    if self.tree[left_grandchild_index] < self.tree[smallest_index] {
192                        smallest_index = left_grandchild_index;
193                        is_grandchild = true;
194                    }
195                }
196
197                if has_right_child(right_child_index, self.size()) {
198                    let right_grandchild_index = right_child(right_child_index);
199                    if self.tree[right_grandchild_index] < self.tree[smallest_index] {
200                        smallest_index = right_grandchild_index;
201                        is_grandchild = true;
202                    }
203                }
204            }
205            (smallest_index, is_grandchild)
206        } else {
207            // node does not have any child
208            (index, false)
209        }
210    }
211
212    // it's like smallest_child_or_grandchild
213    fn greatest_child_or_grandchild(&self, index: usize) -> (usize, bool) {
214        // check left sub tree
215        if has_left_child(index, self.size()) {
216            let left_child_index = left_child(index);
217
218            let mut greatest_index = left_child_index;
219            let mut is_grandchild = false;
220
221            if self.tree[left_child_index] > self.tree[greatest_index] {
222                greatest_index = left_child_index;
223                is_grandchild = false;
224            }
225
226            // check grandchildren of left sub tree
227            if has_left_child(left_child_index, self.size()) {
228                let left_grandchild_index = left_child(left_child_index);
229                if self.tree[left_grandchild_index] > self.tree[greatest_index] {
230                    greatest_index = left_grandchild_index;
231                    is_grandchild = true;
232                }
233            }
234            if has_right_child(left_child_index, self.size()) {
235                let right_grandchild_index = right_child(left_child_index);
236                if self.tree[right_grandchild_index] > self.tree[greatest_index] {
237                    greatest_index = right_grandchild_index;
238                    is_grandchild = true;
239                }
240            }
241
242            // check right sub tree
243            if has_right_child(index, self.size()) {
244                let right_child_index = right_child(index);
245                if self.tree[right_child_index] > self.tree[greatest_index] {
246                    greatest_index = right_child_index;
247                    is_grandchild = false;
248                }
249
250                // check grandchildren of right sub tree
251                if has_left_child(right_child_index, self.size()) {
252                    let left_grandchild_index = left_child(right_child_index);
253                    if self.tree[left_grandchild_index] > self.tree[greatest_index] {
254                        greatest_index = left_grandchild_index;
255                        is_grandchild = true;
256                    }
257                }
258                if has_right_child(right_child_index, self.size()) {
259                    let right_grandchild_index = right_child(right_child_index);
260                    if self.tree[right_grandchild_index] > self.tree[greatest_index] {
261                        greatest_index = right_grandchild_index;
262                        is_grandchild = true;
263                    }
264                }
265            }
266            (greatest_index, is_grandchild)
267        } else {
268            (index, false)
269        }
270    }
271
272    /// Pushes an item into the heap
273    /// * Complexity: O(log n)
274    ///
275    /// # Arguments
276    /// * `item`: data to be pushed into the heap
277    ///
278    /// # Examples
279    /// ```
280    /// use rudac::heap::MinMax;
281    ///
282    /// let mut minmax: MinMax<usize> = MinMax::init();
283    ///
284    /// minmax.push(10);
285    /// minmax.push(5);
286    /// minmax.push(1);
287    /// minmax.push(4);
288    /// minmax.push(3);
289    /// minmax.push(12);
290    ///
291    /// assert_eq!(*minmax.peek_min().unwrap(), 1);
292    /// assert_eq!(*minmax.peek_max().unwrap(), 12);
293    /// ```
294    pub fn push(&mut self, item: T) {
295        // append the data at end of the heap
296        self.tree.push(item);
297
298        // bubble up the node until heap property is restored
299        self.push_up(self.tree.len() - 1);
300    }
301
302    // bubbles up a node until heap property is restored
303    fn push_up(&mut self, index: usize) {
304        // nodes other than root can be pushed up
305        if index != 0 {
306            if is_on_min_level(index) {
307                // if node is on a min level but is greater than its parent, node can replace its parent
308                // parent must be pushed up as a max node
309                if self.tree[index] > self.tree[parent(index)] {
310                    self.tree.swap(index, parent(index));
311                    self.push_up_max(parent(index));
312                } else {
313                    // push up the node as a min node
314                    self.push_up_min(index);
315                }
316            } else {
317                // if node is on a max level but is smaller than its parent, node can replace its parent
318                // parent must be pushed up as a min node
319                if self.tree[index] < self.tree[parent(index)] {
320                    self.tree.swap(index, parent(index));
321                    self.push_up_min(parent(index));
322                } else {
323                    // push up the node as a max node
324                    self.push_up_max(index);
325                }
326            }
327        }
328    }
329
330    // bubbles up a node until heap property is restored
331    fn push_up_min(&mut self, mut index: usize) {
332        // until node is smaller than its grandparent, swap them and iterate to the top of the heap
333        while has_grandparent(index) && self.tree[index] < self.tree[grandparent(index)] {
334            self.tree.swap(index, grandparent(index));
335
336            index = grandparent(index);
337        }
338    }
339
340    // bubbles up a node until heap property is restored
341    fn push_up_max(&mut self, mut index: usize) {
342        // until node is greater than its grandparent, swap them and iterate to the top of the heap
343        while has_grandparent(index) && self.tree[index] > self.tree[grandparent(index)] {
344            self.tree.swap(index, grandparent(index));
345
346            index = grandparent(index);
347        }
348    }
349
350    /// Returns a reference to the min value. returns None if heap is empty
351    /// * Complexity: O(1)
352    ///
353    /// # Examples
354    /// ```
355    /// use rudac::heap::MinMax;
356    ///
357    /// let minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);
358    ///
359    /// assert_eq!(*minmax.peek_min().unwrap(), 1);
360    /// ```
361    pub fn peek_min(&self) -> Option<&T> {
362        if self.is_empty() {
363            return None;
364        }
365
366        Some(&self.tree[0])
367    }
368
369    /// Returns a reference to the max value. returns None if heap is empty
370    /// * Complexity: O(1)
371    ///
372    /// # Examples
373    /// ```
374    /// use rudac::heap::MinMax;
375    ///
376    /// let minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);
377    ///
378    /// assert_eq!(*minmax.peek_max().unwrap(), 11);
379    /// ```
380    pub fn peek_max(&self) -> Option<&T> {
381        match self.size() {
382            0 => None,                // if heap is empty return None
383            1 => Some(&self.tree[0]), // if there is only one item, it is max
384            2 => Some(&self.tree[1]), // if there are only two item, item at index 1 is max
385            _ => {
386                // if there are more than 2 items, max is either at index 1 or 2
387                if self.tree[1] > self.tree[2] {
388                    Some(&self.tree[1])
389                } else {
390                    Some(&self.tree[2])
391                }
392            }
393        }
394    }
395
396    /// Pops min value from heap and returns it. returns None if heap is empty
397    /// * Complexity: O(log n)
398    ///
399    /// # Examples
400    /// ```
401    /// use rudac::heap::MinMax;
402    ///
403    /// let mut minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);
404    ///
405    /// assert_eq!(minmax.pop_min().unwrap(), 1);
406    /// assert_eq!(*minmax.peek_min().unwrap(), 2);
407    /// ```
408    pub fn pop_min(&mut self) -> Option<T> {
409        match self.size() {
410            0 => None,                           // if heap is empty return None
411            1 => Some(self.tree.pop().unwrap()), // if there is only one item, it is min
412            _ => {
413                let mut last_item = self.tree.pop().unwrap(); // pop last leaf
414
415                std::mem::swap(&mut last_item, &mut self.tree[0]); // swap min with leaf
416                self.push_down(0); // push down the leaf until heap property is restored
417                Some(last_item) // return min node
418            }
419        }
420    }
421
422    /// Pops max value from heap and returns it. returns None if heap is empty
423    /// * Complexity: O(log n)
424    ///
425    /// # Examples
426    /// ```
427    /// use rudac::heap::MinMax;
428    ///
429    /// let mut minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);
430    ///
431    /// assert_eq!(minmax.pop_max().unwrap(), 11);
432    /// assert_eq!(*minmax.peek_max().unwrap(), 9);
433    /// ```
434    pub fn pop_max(&mut self) -> Option<T> {
435        match self.size() {
436            0 => None,                               // if heap is empty, return None
437            1 | 2 => Some(self.tree.pop().unwrap()), // if there are only 1 or 2 item, max is at the end of the heap
438            _ => {
439                // if there are more than 2 items, max is at index 1 or 2
440                let mut last_item: T;
441
442                if self.tree[1] > self.tree[2] {
443                    last_item = self.tree.pop().unwrap(); // pop last leaf
444                    std::mem::swap(&mut last_item, &mut self.tree[1]); // swap max with leaf
445                    self.push_down(1); // push down leaf until heap property is restored
446                } else {
447                    last_item = self.tree.pop().unwrap();
448                    std::mem::swap(&mut last_item, &mut self.tree[2]);
449                    self.push_down(2);
450                }
451
452                Some(last_item)
453            }
454        }
455    }
456
457    /// Pops and returns the min value and pushes the `item` into heap without allocating.
458    /// * Complexity: O(log n)
459    ///
460    /// # Arguments
461    /// * `item`: data to be pushed into the heap
462    ///
463    /// # Examples
464    /// ```
465    /// use rudac::heap::MinMax;
466    ///
467    /// let mut minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 0]);
468    ///
469    /// assert_eq!(minmax.push_pop_min(13).unwrap(), 0);
470    /// assert_eq!(*minmax.peek_min().unwrap(), 2);
471    /// assert_eq!(*minmax.peek_max().unwrap(), 13);
472    /// ```
473    pub fn push_pop_min(&mut self, mut item: T) -> Option<T> {
474        // if heap is empty or item is already smaller than min value in heap,
475        // nothing should be done just return the item
476        if self.is_empty() || item < self.tree[0] {
477            return Some(item);
478        }
479
480        // swap the min value with item
481        std::mem::swap(&mut item, &mut self.tree[0]);
482
483        // push down item until heap property is restored
484        self.push_down(0);
485
486        // return min
487        return Some(item);
488    }
489
490    /// Pops and returns the max value and pushes the `item` into heap without allocating.
491    /// * Complexity: O(log n)
492    ///
493    /// # Arguments
494    /// * `item`: data to be pushed into the heap
495    ///
496    /// # Examples
497    /// ```
498    /// use rudac::heap::MinMax;
499    ///
500    /// let mut minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);
501    ///
502    /// assert_eq!(minmax.push_pop_max(0).unwrap(), 11);
503    /// assert_eq!(*minmax.peek_min().unwrap(), 0);
504    /// assert_eq!(*minmax.peek_max().unwrap(), 9);
505    /// ```
506    pub fn push_pop_max(&mut self, mut item: T) -> Option<T> {
507        match self.size() {
508            0 => Some(item), // if heap is empty just return the item
509            _ => {
510                let max_index = self.find_max_index(); // find index of maximum value in heap
511
512                // if item is already greater than the max value in heap, just return the item
513                if item > self.tree[max_index] {
514                    Some(item)
515                } else {
516                    std::mem::swap(&mut item, &mut self.tree[max_index]);
517
518                    // check if `item` is smaller than root
519                    if self.tree[max_index] < self.tree[0] {
520                        self.tree.swap(max_index, 0);
521                    }
522                    // push down item(or previous root) to restore heap property
523                    self.push_down(max_index);
524
525                    // return max
526                    Some(item)
527                }
528            }
529        }
530    }
531
532    /// Pops and returns the min value and pushes the `item` into heap without allocating.
533    /// * Complexity: O(log n)
534    ///
535    /// # Arguments
536    /// * `item`: data to be pushed into the heap
537    ///
538    /// # Examples
539    /// ```
540    /// use rudac::heap::MinMax;
541    ///
542    /// let mut minmax: MinMax<usize> = MinMax::build_heap(vec![3, 2, 1]);
543    ///     
544    /// assert_eq!(minmax.replace_min(4).unwrap(), 1);
545    /// assert_eq!(*minmax.peek_min().unwrap(), 2);
546    /// assert_eq!(*minmax.peek_max().unwrap(), 4);
547    /// ```
548    pub fn replace_min(&mut self, mut item: T) -> Option<T> {
549        // if heap is empty just push the item
550        if self.is_empty() {
551            self.push(item);
552            return None;
553        }
554
555        // replace min with item
556        std::mem::swap(&mut item, &mut self.tree[0]);
557
558        // push down item until heap property is restored
559        self.push_down(0);
560
561        // return min
562        Some(item)
563    }
564
565    /// Pops and returns the max value and pushes the `item` into heap without allocating.
566    /// * Complexity: O(log n)
567    ///
568    /// # Arguments
569    /// * `item`: data to be pushed into the heap
570    ///
571    /// # Examples
572    /// ```
573    /// use rudac::heap::MinMax;
574    ///
575    /// let mut minmax: MinMax<usize> = MinMax::build_heap(vec![3, 2, 1]);
576    ///
577    /// assert_eq!(minmax.replace_max(4).unwrap(), 3);
578    /// assert_eq!(*minmax.peek_min().unwrap(), 1);
579    /// assert_eq!(*minmax.peek_max().unwrap(), 4);
580    /// ```
581    pub fn replace_max(&mut self, mut item: T) -> Option<T> {
582        // if heap is empty just push the item
583        if self.is_empty() {
584            self.push(item);
585            return None;
586        }
587
588        // find index of node with max value
589        let max_index = self.find_max_index();
590
591        // swap max value with item
592        std::mem::swap(&mut item, &mut self.tree[max_index]);
593
594        // check if item is smaller than root
595        if self.tree[max_index] < self.tree[0] {
596            self.tree.swap(max_index, 0);
597        }
598
599        // push down item(or previous root) until heap property is restored
600        self.push_down(max_index);
601
602        // return max
603        Some(item)
604    }
605    // find index of node with maximum value
606    fn find_max_index(&self) -> usize {
607        match self.size() {
608            0 => panic!("There is no item is the heap."),
609            1 => 0, // if there is only one item, it's max
610            2 => 1, // if there are only two items, max has index 1
611            _ => {
612                // if there are more than 2 items in heap, max is in index 1 or 2
613                if self.tree[1] > self.tree[2] {
614                    1
615                } else {
616                    2
617                }
618            }
619        }
620    }
621
622    /// Reserves capacity for `additional` more items to be pushed into heap
623    pub fn reserve(&mut self, additional: usize) {
624        self.tree.reserve(additional);
625    }
626
627    /// Reserves capacity for `additional` more items to be pushed into heap
628    pub fn reserve_exact(&mut self, additional: usize) {
629        self.tree.reserve_exact(additional);
630    }
631
632    /// Shrinks capacity internal vector to fit the existing data
633    pub fn shrink_to_fit(&mut self) {
634        self.tree.shrink_to_fit();
635    }
636
637    /// Consumes the heap and returns the internal vector
638    pub fn into_vec(self) -> Vec<T> {
639        self.tree
640    }
641
642    /// Total number of elements in the heap
643    pub fn size(&self) -> usize {
644        self.tree.len()
645    }
646
647    /// Returns true if heap is empty, false otherwise
648    pub fn is_empty(&self) -> bool {
649        self.size() == 0
650    }
651
652    /// Clears the internal vector
653    pub fn clear(&mut self) {
654        self.tree.clear()
655    }
656
657    /// Returns capacity of the heap
658    pub fn capacity(&self) -> usize {
659        self.tree.capacity()
660    }
661}
662
663fn is_on_min_level(index: usize) -> bool {
664    (((index + 1) as f32).log(2.0) as usize) % 2 == 0
665}
666
667fn has_grandparent(index: usize) -> bool {
668    index > 2
669}
670
671// fn has_parent(index: usize) -> bool {
672//     index > 0
673// }
674
675fn has_left_child(index: usize, size: usize) -> bool {
676    (2 * (index + 1)) - 1 < size
677}
678
679fn has_right_child(index: usize, size: usize) -> bool {
680    (2 * (index + 1)) < size
681}
682
683fn has_child(index: usize, size: usize) -> bool {
684    has_left_child(index, size) || has_left_child(index, size)
685}
686
687fn left_child(index: usize) -> usize {
688    (2 * (index + 1)) - 1
689}
690
691fn right_child(index: usize) -> usize {
692    2 * (index + 1)
693}
694
695pub fn parent(index: usize) -> usize {
696    (index - 1) / 2
697}
698
699pub fn grandparent(index: usize) -> usize {
700    parent(parent(index))
701}
702
703#[cfg(test)]
704mod tests {
705    use super::*;
706
707    #[test]
708    fn heap_minmax_tree_is_on_min_level() {
709        assert_eq!(is_on_min_level(0), true);
710
711        assert_eq!(is_on_min_level(1), false);
712        assert_eq!(is_on_min_level(2), false);
713
714        assert_eq!(is_on_min_level(3), true);
715        assert_eq!(is_on_min_level(4), true);
716        assert_eq!(is_on_min_level(5), true);
717        assert_eq!(is_on_min_level(6), true);
718
719        assert_eq!(is_on_min_level(7), false);
720    }
721
722    #[test]
723    fn heap_minmax_tree_has_grandparent() {
724        assert_eq!(has_grandparent(0), false);
725        assert_eq!(has_grandparent(1), false);
726        assert_eq!(has_grandparent(2), false);
727        assert_eq!(has_grandparent(3), true);
728    }
729
730    #[test]
731    fn heap_minmax_tree_parent() {
732        assert_eq!(parent(1), 0);
733        assert_eq!(parent(2), 0);
734        assert_eq!(parent(3), 1);
735        assert_eq!(parent(4), 1);
736        assert_eq!(parent(5), 2);
737        assert_eq!(parent(6), 2);
738        assert_eq!(parent(7), 3);
739        assert_eq!(parent(8), 3);
740        assert_eq!(parent(9), 4);
741        assert_eq!(parent(10), 4);
742        assert_eq!(parent(11), 5);
743        assert_eq!(parent(12), 5);
744        assert_eq!(parent(13), 6);
745        assert_eq!(parent(14), 6);
746    }
747
748    #[test]
749    fn heap_minmax_tree_grandparent() {
750        assert_eq!(grandparent(3), 0);
751        assert_eq!(grandparent(4), 0);
752        assert_eq!(grandparent(5), 0);
753        assert_eq!(grandparent(6), 0);
754        assert_eq!(grandparent(7), 1);
755        assert_eq!(grandparent(8), 1);
756        assert_eq!(grandparent(9), 1);
757        assert_eq!(grandparent(10), 1);
758        assert_eq!(grandparent(11), 2);
759        assert_eq!(grandparent(12), 2);
760        assert_eq!(grandparent(13), 2);
761        assert_eq!(grandparent(14), 2);
762    }
763
764    #[test]
765    fn heap_minmax_tree_has_left_child() {
766        assert_eq!(has_left_child(0, 6), true);
767        assert_eq!(has_left_child(1, 6), true);
768        assert_eq!(has_left_child(2, 6), true);
769        assert_eq!(has_left_child(3, 6), false);
770        assert_eq!(has_left_child(4, 6), false);
771        assert_eq!(has_left_child(5, 6), false);
772    }
773
774    #[test]
775    fn heap_minmax_tree_has_right_child() {
776        assert_eq!(has_right_child(0, 6), true);
777        assert_eq!(has_right_child(1, 6), true);
778        assert_eq!(has_right_child(2, 6), false);
779        assert_eq!(has_right_child(3, 6), false);
780        assert_eq!(has_right_child(4, 6), false);
781        assert_eq!(has_right_child(5, 6), false);
782    }
783
784    #[test]
785    fn heap_minmax_tree_has_child() {
786        assert_eq!(has_child(0, 6), true);
787        assert_eq!(has_child(1, 6), true);
788        assert_eq!(has_child(2, 6), true);
789        assert_eq!(has_child(3, 6), false);
790        assert_eq!(has_child(4, 6), false);
791        assert_eq!(has_child(5, 6), false);
792    }
793
794    #[test]
795    fn heap_minmax_tree_left_child() {
796        assert_eq!(left_child(0), 1);
797        assert_eq!(left_child(1), 3);
798        assert_eq!(left_child(2), 5);
799        assert_eq!(left_child(3), 7);
800        assert_eq!(left_child(4), 9);
801        assert_eq!(left_child(5), 11);
802    }
803
804    #[test]
805    fn heap_minmax_tree_right_child() {
806        assert_eq!(right_child(0), 2);
807        assert_eq!(right_child(1), 4);
808        assert_eq!(right_child(2), 6);
809        assert_eq!(right_child(3), 8);
810        assert_eq!(right_child(4), 10);
811        assert_eq!(right_child(5), 12);
812    }
813
814    #[test]
815    fn heap_minmax_init() {
816        let minmax: MinMax<usize> = MinMax::init();
817
818        assert_eq!(minmax.size(), 0);
819        assert_eq!(minmax.is_empty(), true);
820        assert_eq!(minmax.capacity(), 0);
821    }
822
823    #[test]
824    fn heap_minmax_with_capacity() {
825        let minmax: MinMax<usize> = MinMax::with_capacity(10);
826
827        assert_eq!(minmax.is_empty(), true);
828        assert_eq!(minmax.size(), 0);
829        assert_eq!(minmax.capacity(), 10);
830    }
831
832    #[test]
833    fn heap_minmax_smallest_child_or_grandchild_1() {
834        let mut minmax: MinMax<usize> = MinMax::init();
835
836        minmax.tree = vec![0, 5, 4, 3, 4, 1];
837
838        assert_eq!(minmax.smallest_child_or_grandchild(0), (5, true));
839        assert_eq!(minmax.smallest_child_or_grandchild(1), (3, false));
840        assert_eq!(minmax.smallest_child_or_grandchild(2), (5, false));
841        assert_eq!(minmax.smallest_child_or_grandchild(3), (3, false));
842        assert_eq!(minmax.smallest_child_or_grandchild(4), (4, false));
843        assert_eq!(minmax.smallest_child_or_grandchild(5), (5, false));
844    }
845
846    #[test]
847    fn heap_minmax_greatest_child_or_grandchild_1() {
848        let mut minmax: MinMax<usize> = MinMax::init();
849
850        minmax.tree = vec![0, 5, 4, 3, 4, 1];
851
852        assert_eq!(minmax.greatest_child_or_grandchild(0), (1, false));
853        assert_eq!(minmax.greatest_child_or_grandchild(1), (4, false));
854        assert_eq!(minmax.greatest_child_or_grandchild(2), (5, false));
855        assert_eq!(minmax.greatest_child_or_grandchild(3), (3, false));
856        assert_eq!(minmax.greatest_child_or_grandchild(4), (4, false));
857        assert_eq!(minmax.greatest_child_or_grandchild(5), (5, false));
858    }
859
860    #[test]
861    fn heap_minmax_push_down_1() {
862        let mut minmax: MinMax<usize> = MinMax::init();
863
864        minmax.tree = vec![0, 5, 4, 3, 4, 1];
865
866        minmax.tree[0] = 6;
867        minmax.push_down(0);
868        assert_eq!(
869            format!("{:?}", minmax.tree),
870            String::from("[1, 5, 6, 3, 4, 4]")
871        );
872
873        minmax.tree[0] = 7;
874        minmax.push_down(0);
875        assert_eq!(
876            format!("{:?}", minmax.tree),
877            String::from("[3, 7, 6, 5, 4, 4]")
878        );
879    }
880
881    #[test]
882    fn heap_minmax_build_heap_1() {
883        let minmax = MinMax::build_heap(vec![1, 3, 0, 6, 8, 2, 4]);
884
885        assert_eq!(minmax.size(), 7);
886        assert_eq!(
887            format!("{:?}", minmax.tree),
888            String::from("[0, 8, 4, 6, 3, 2, 1]")
889        );
890    }
891
892    #[test]
893    fn heap_minmax_build_heap_2() {
894        let minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 0]);
895
896        assert_eq!(minmax.size(), 10);
897        assert_eq!(
898            format!("{:?}", minmax.tree),
899            String::from("[0, 9, 11, 3, 4, 5, 2, 6, 7, 8]")
900        );
901    }
902
903    #[test]
904    fn heap_minmax_peek_min_1() {
905        let minmax: MinMax<usize> = MinMax::init();
906
907        assert_eq!(minmax.peek_min(), None);
908    }
909
910    #[test]
911    fn heap_minmax_peek_min_2() {
912        let mut minmax: MinMax<usize> = MinMax::init();
913
914        minmax.push(0);
915
916        assert_eq!(*minmax.peek_min().unwrap(), 0);
917    }
918
919    #[test]
920    fn heap_minmax_peek_min_3() {
921        let mut minmax: MinMax<usize> = MinMax::init();
922
923        minmax.push(10);
924        minmax.push(0);
925
926        assert_eq!(*minmax.peek_min().unwrap(), 0);
927    }
928
929    #[test]
930    fn heap_minmax_peek_max_1() {
931        let minmax: MinMax<usize> = MinMax::init();
932
933        assert_eq!(minmax.peek_max(), None);
934    }
935
936    #[test]
937    fn heap_minmax_peek_max_2() {
938        let mut minmax: MinMax<usize> = MinMax::init();
939
940        minmax.push(0);
941
942        assert_eq!(*minmax.peek_max().unwrap(), 0);
943    }
944
945    #[test]
946    fn heap_minmax_peek_max_3() {
947        let mut minmax: MinMax<usize> = MinMax::init();
948
949        minmax.push(10);
950        minmax.push(0);
951
952        assert_eq!(*minmax.peek_max().unwrap(), 10);
953    }
954
955    #[test]
956    fn heap_minmax_peek_max_4() {
957        let mut minmax: MinMax<usize> = MinMax::init();
958
959        minmax.push(10);
960        minmax.push(0);
961        minmax.push(20);
962
963        assert_eq!(*minmax.peek_max().unwrap(), 20);
964    }
965
966    #[test]
967    fn heap_minmax_push_1() {
968        let mut minmax: MinMax<usize> = MinMax::init();
969
970        minmax.push(10);
971
972        assert_eq!(*minmax.peek_min().unwrap(), 10);
973        assert_eq!(*minmax.peek_max().unwrap(), 10);
974    }
975
976    #[test]
977    fn heap_minmax_push_2() {
978        let mut minmax: MinMax<usize> = MinMax::init();
979
980        minmax.push(10);
981        minmax.push(5);
982        minmax.push(1);
983        minmax.push(4);
984        minmax.push(3);
985        minmax.push(12);
986
987        assert_eq!(*minmax.peek_min().unwrap(), 1);
988        assert_eq!(*minmax.peek_max().unwrap(), 12);
989    }
990
991    #[test]
992    fn heap_minmax_pop_min() {
993        let mut minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 0]);
994
995        assert_eq!(*minmax.peek_min().unwrap(), 0);
996
997        minmax.pop_min();
998        assert_eq!(*minmax.peek_min().unwrap(), 2);
999
1000        minmax.pop_min();
1001        assert_eq!(*minmax.peek_min().unwrap(), 3);
1002
1003        minmax.pop_min();
1004        assert_eq!(*minmax.peek_min().unwrap(), 4);
1005
1006        minmax.pop_min();
1007        assert_eq!(*minmax.peek_min().unwrap(), 5);
1008
1009        minmax.pop_min();
1010        assert_eq!(*minmax.peek_min().unwrap(), 6);
1011
1012        minmax.pop_min();
1013        assert_eq!(*minmax.peek_min().unwrap(), 7);
1014
1015        minmax.pop_min();
1016        assert_eq!(*minmax.peek_min().unwrap(), 8);
1017
1018        minmax.pop_min();
1019        assert_eq!(*minmax.peek_min().unwrap(), 9);
1020
1021        minmax.pop_min();
1022        assert_eq!(*minmax.peek_min().unwrap(), 11);
1023
1024        minmax.pop_min();
1025        assert_eq!(minmax.peek_min(), None);
1026    }
1027
1028    #[test]
1029    fn heap_minmax_pop_max() {
1030        let mut minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 0]);
1031
1032        assert_eq!(*minmax.peek_max().unwrap(), 11);
1033
1034        minmax.pop_max();
1035        assert_eq!(*minmax.peek_max().unwrap(), 9);
1036
1037        minmax.pop_max();
1038        assert_eq!(*minmax.peek_max().unwrap(), 8);
1039
1040        minmax.pop_max();
1041        assert_eq!(*minmax.peek_max().unwrap(), 7);
1042
1043        minmax.pop_max();
1044        assert_eq!(*minmax.peek_max().unwrap(), 6);
1045
1046        minmax.pop_max();
1047        assert_eq!(*minmax.peek_max().unwrap(), 5);
1048
1049        minmax.pop_max();
1050        assert_eq!(*minmax.peek_max().unwrap(), 4);
1051
1052        minmax.pop_max();
1053        assert_eq!(*minmax.peek_max().unwrap(), 3);
1054
1055        minmax.pop_max();
1056        assert_eq!(*minmax.peek_max().unwrap(), 2);
1057
1058        minmax.pop_max();
1059        assert_eq!(*minmax.peek_max().unwrap(), 0);
1060
1061        minmax.pop_max();
1062        assert_eq!(minmax.peek_max(), None);
1063    }
1064
1065    #[test]
1066    fn heap_minmax_push_pop_min_1() {
1067        let mut minmax = MinMax::init();
1068
1069        assert_eq!(minmax.push_pop_min(1).unwrap(), 1);
1070    }
1071
1072    #[test]
1073    fn heap_minmax_push_pop_min_2() {
1074        let mut minmax = MinMax::init();
1075        minmax.push(2);
1076
1077        assert_eq!(minmax.push_pop_min(1).unwrap(), 1);
1078    }
1079
1080    #[test]
1081    fn heap_minmax_push_pop_min_3() {
1082        let mut minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 0]);
1083
1084        assert_eq!(minmax.push_pop_min(13).unwrap(), 0);
1085        assert_eq!(*minmax.peek_min().unwrap(), 2);
1086        assert_eq!(*minmax.peek_max().unwrap(), 13);
1087    }
1088
1089    #[test]
1090    fn heap_minmax_push_pop_max_1() {
1091        let mut minmax = MinMax::init();
1092
1093        assert_eq!(minmax.push_pop_max(1).unwrap(), 1);
1094    }
1095
1096    #[test]
1097    fn heap_minmax_push_pop_max_2() {
1098        let mut minmax = MinMax::init();
1099        minmax.push(2);
1100
1101        assert_eq!(minmax.push_pop_max(3).unwrap(), 3);
1102    }
1103
1104    #[test]
1105    fn heap_minmax_push_pop_max_3() {
1106        let mut minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);
1107
1108        assert_eq!(minmax.push_pop_max(0).unwrap(), 11);
1109        assert_eq!(*minmax.peek_min().unwrap(), 0);
1110        assert_eq!(*minmax.peek_max().unwrap(), 9);
1111    }
1112
1113    #[test]
1114    fn heap_minmax_replace_min_1() {
1115        let mut minmax: MinMax<usize> = MinMax::build_heap(vec![]);
1116
1117        assert_eq!(minmax.replace_min(0), None);
1118        assert_eq!(*minmax.peek_min().unwrap(), 0);
1119        assert_eq!(*minmax.peek_max().unwrap(), 0);
1120    }
1121
1122    #[test]
1123    fn heap_minmax_replace_min_2() {
1124        let mut minmax: MinMax<usize> = MinMax::build_heap(vec![3, 2, 1]);
1125
1126        assert_eq!(minmax.replace_min(4).unwrap(), 1);
1127        assert_eq!(*minmax.peek_min().unwrap(), 2);
1128        assert_eq!(*minmax.peek_max().unwrap(), 4);
1129    }
1130
1131    #[test]
1132    fn heap_minmax_replace_max_1() {
1133        let mut minmax: MinMax<usize> = MinMax::build_heap(vec![]);
1134
1135        assert_eq!(minmax.replace_max(0), None);
1136        assert_eq!(*minmax.peek_min().unwrap(), 0);
1137        assert_eq!(*minmax.peek_max().unwrap(), 0);
1138    }
1139
1140    #[test]
1141    fn heap_minmax_replace_max_2() {
1142        let mut minmax: MinMax<usize> = MinMax::build_heap(vec![3, 2, 1]);
1143
1144        assert_eq!(minmax.replace_max(4).unwrap(), 3);
1145        assert_eq!(*minmax.peek_min().unwrap(), 1);
1146        assert_eq!(*minmax.peek_max().unwrap(), 4);
1147    }
1148
1149    #[test]
1150    fn heap_minmax_replace_max_3() {
1151        let mut minmax: MinMax<usize> = MinMax::build_heap(vec![3, 2, 1]);
1152
1153        assert_eq!(minmax.replace_max(0).unwrap(), 3);
1154        assert_eq!(*minmax.peek_min().unwrap(), 0);
1155        assert_eq!(*minmax.peek_max().unwrap(), 2);
1156    }
1157}
rudac/heap/minmax.rs

rudac/heap/
minmax.rs
