-
Notifications
You must be signed in to change notification settings - Fork 34
/
FibHeap.java
146 lines (116 loc) · 3.25 KB
/
FibHeap.java
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
public class FibHeap {
public Node min;
public int numNodes;
public FibHeap() {
this.min = null;
this.numNodes = 0;
}
public void insertNode(int key, int vertVal) {
Node x = new Node(key, vertVal);
this.min = mergeLists(this.min, x);
this.numNodes += 1;
}
public void insertNode(Node x) {
// part of extract min function
this.min = mergeLists(this.min, x);
}
public Node mergeLists(Node a, Node b) {
if (a == null && b == null)
return null;
if (a == null)
return b;
if (b == null)
return a;
Node temp = a.next;
a.next = b.next;
a.next.prev = a;
b.next = temp;
b.next.prev = b;
return (a.key < b.key) ? a : b;
}
public Node extractMin() {
if(this.min == null) {
System.out.println("Underflow");
return null;
}
else {
Node child = this.min.child;
if(child != null) {
while(child.next != child) {
Node temp = child;
child.next.prev = child.prev;
child.prev.next = child.next;
child = child.next;
temp.next = temp;
temp.prev = temp;
temp.parent = null;
insertNode(temp);
}
child.parent = null;
insertNode(child);
}
Node z = this.min;
if (z == z.next){
this.min = null;
return z;
}
else {
this.min = z.next;
z.next.prev = z.prev;
z.prev.next = z.next;
z.next = z;
z.prev = z;
// consolidate()
return z;
}
}
}
public void consolidate() {
int D = (int) (Math.log(this.numNodes) / Math.log(2));
D += 1;
Node[] array = new Node[D];
for (Node i : array ) {
i = null;
}
}
public void printList(Node x) {
if (x == null) {
System.out.println("||");
return;
}
Node temp = x;
System.out.print(x.key + " --> ");
temp = temp.next;
while(temp != x){
System.out.print(temp.key + " --> ");
temp = temp.next;
}
System.out.println( "||");
}
public static void main(String[] args) {
FibHeap H = new FibHeap();
H.insertNode(1,0);
H.insertNode(2,0);
H.printList(H.min);
H.extractMin();
H.printList(H.min);
H.extractMin();
H.printList(H.min);
}
}
class Node {
public Node(int key, int vertVal) {
this.key = key;
this.vertVal = vertVal;
this.next = this;
this.prev = this;
}
public int key;
public int vertVal; // Value of vertex in graph
public Node child = null;
public Node parent = null;
public Node next = null;
public Node prev = null;
public boolean isMarked = false;
public int degree = 0;
}