CS5110-Fall2019/FibonacciHeapDriver.java at master · dixoncs/CS5110-Fall2019 · GitHub

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
//import java.util.*;

/**
 * Fibonacci Heap driver class.
 * @author Courtney Dixon
 * @version 11/9/2019
 */
public class FibonacciHeapDriver {

    /**
     * Main method.
     * @param args command-line arguments
     */
    public static void main(String[] args) {
        FibonacciHeap fh = new FibonacciHeap();

        System.out.println("Running test 1");
        FibonacciNode n1 = new FibonacciNode(6);
        FibonacciNode n2 = new FibonacciNode(4);
        FibonacciNode n3 = new FibonacciNode(8);
        fh.insert(n1);
        fh.insert(n2);
        fh.insert(n3);

        System.out.println("-----------------------------------------------------");
        System.out.println("Testing insert. Heap should contain 4,6,8");
        fh.displayHeap();
        System.out.println("-----------------------------------------------------\n");

        System.out.println("-----------------------------------------------------");
        System.out.println("Decreasing key of n2 (4) to 3");
        fh.decreaseKey(n2, 3);
        fh.displayHeap();
        System.out.println("-----------------------------------------------------\n");

        System.out.println("-----------------------------------------------------");
        System.out.println(("Testing find min. Should return 3"));
        System.out.println(fh.findMin().key);
        System.out.println("-----------------------------------------------------\n");

        System.out.println("-----------------------------------------------------");
        System.out.println("Testing delete min. Heap should contain 6,8");
        fh.deleteMin();
        System.out.println("The new min should be 6. Min is: " + fh.findMin().key);
        fh.displayHeap();
        System.out.println("-----------------------------------------------------\n");
        System.out.println("-----------------------------------------------------");
        System.out.println("Testing delete on 6. Heap should contain 8");
        fh.delete(n1);
        System.out.println("The new min should be 8. Min is: " + fh.findMin().key);
        fh.displayHeap();
        System.out.println("-----------------------------------------------------\n");

        System.out.println("-----------------------------------------------------");
        System.out.println("Testing delete on 8. Heap should contain nothing.");
        fh.delete(n3);
        System.out.println("The new min should be null. Min is: " + fh.findMin());
        fh.displayHeap();
        System.out.println("-----------------------------------------------------\n");

        System.out.println("Running test 2");
        FibonacciNode n4 = new FibonacciNode(6);
        FibonacciNode n5 = new FibonacciNode(4);
        FibonacciNode n6 = new FibonacciNode(8);
        fh.insert(n4);
        fh.insert(n5);
        fh.insert(n6);

        System.out.println("-----------------------------------------------------");
        System.out.println("Testing insert. Heap should contain 4,6,8");
        fh.displayHeap();
        System.out.println("-----------------------------------------------------\n");

        System.out.println("-----------------------------------------------------");
        System.out.println("Decreasing key of n4 (4) to 3");
        fh.decreaseKey(n4, 3);
        fh.displayHeap();
        System.out.println("-----------------------------------------------------\n");

        System.out.println("-----------------------------------------------------");
        System.out.println(("Testing find min. Should return 3"));
        System.out.println(fh.findMin().key);
        System.out.println("-----------------------------------------------------\n");

        System.out.println("-----------------------------------------------------");
        System.out.println("Testing delete min. Heap should contain 6,8");
        fh.deleteMin();
        System.out.println("The new min should be 6. Min is: " + fh.findMin().key);
        fh.displayHeap();
        System.out.println("-----------------------------------------------------\n");

        System.out.println("-----------------------------------------------------");
        System.out.println("Testing delete on 8. Heap should contain 6");
        fh.delete(n6);
        System.out.println("The new min should be 6. Min is: " + fh.findMin().key);
        fh.displayHeap();
        System.out.println("-----------------------------------------------------\n");

        System.out.println("-----------------------------------------------------");
        System.out.println("Testing delete on 6. Heap should contain nothing.");
        fh.delete(n5);
        System.out.println("The new min should be null. Min is: " + fh.findMin());
        fh.displayHeap();
        System.out.println("-----------------------------------------------------\n");


    }
}