mheap 0.1.1

Flexible binary heaps
Documentation 
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

use mheap::{MaxHeap, MinHeap, IndexableHeap, VecHeap};

#[test]
fn min_heap() {
    let mut heap = VecHeap::<i32, MinHeap>::new();
    heap.push(3);
    heap.push(15);
    heap.push(1);
    heap.push(42);
    heap.push(7);
    heap.push(6);
    heap.push(5);
    heap.push(64);

    let mut data = Vec::new();
    while let Some(x) = heap.pop() {
        data.push(x);
    }
    assert_eq!(data, vec![1, 3, 5, 6, 7, 15, 42, 64]);
}

#[test]
fn max_heap() {
    let mut heap = VecHeap::<i32, MaxHeap>::new();
    heap.push(3);
    heap.push(15);
    heap.push(1);
    heap.push(42);
    heap.push(7);
    heap.push(6);
    heap.push(5);
    heap.push(64);

    let mut data = Vec::new();
    while let Some(x) = heap.pop() {
        data.push(x);
    }
    assert_eq!(data, vec![64, 42, 15, 7, 6, 5, 3, 1]);
}

#[test]
fn unordered_heap() {
    let mut heap = IndexableHeap::<i32, MinHeap>::new();
    heap.push(3);
    heap.push(15);
    heap.push(1);
    let idx = heap.push(42);
    heap.push(7);
    heap.push(6);
    heap.push(5);
    heap.push(64);

    let mut data = Vec::new();
    for _ in 0..2 {
        data.push(heap.pop().unwrap());
    }

    let entry = heap.by_index_mut(idx);
    assert_eq!(*entry, 42);
    assert_eq!(entry.index(), idx);
    drop(entry);

    while let Some(x) = heap.pop() {
        data.push(x);
    }
    assert_eq!(data, vec![1, 3, 5, 6, 7, 15, 42, 64]);
}

#[test]
fn unordered_heap_mut() {
    let mut heap = IndexableHeap::<i32, MinHeap>::new();
    heap.push(3);
    heap.push(15);
    heap.push(1);
    let idx = heap.push(42);
    heap.push(7);
    heap.push(6);
    heap.push(5);
    heap.push(64);

    let mut data = Vec::new();
    for _ in 0..2 {
        data.push(heap.pop().unwrap());
    }

    *heap.by_index_mut(idx) = 1;

    while let Some(x) = heap.pop() {
        data.push(x);
    }
    assert_eq!(data, vec![1, 3, 1, 5, 6, 7, 15, 64]);
}