Repository navigation
Expand file tree
/
Copy pathFibonacciHeap.java
More file actions
426 lines (371 loc) · 12.7 KB
/
Copy pathFibonacciHeap.java
File metadata and controls
426 lines (371 loc) · 12.7 KB
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
// id1: 212640684
//name1: yahli weiss
// username1: yahliweiss
// id2: 315084442
//name2: amit dako
//username2: amitdako
/**
* FibonacciHeap
*
* An implementation of Fibonacci heap over positive integers.
*
*/
public class FibonacciHeap {
public HeapNode min; // pointer to minimal root - initialized to 0
public int fibSize; // number of nodes in the heap - initialized to 0
public int numOfCuts; // number of cuts done on the heap - initialized to 0
public int numOfLinks; // number of links done on the heap - initialized to 0
public int numOfTrees; // number of roots in the heap- initialzed to 0
/**
*
* Constructor to initialize an empty heap.
*
*/
public FibonacciHeap() {
}
/**
*
* pre: key > 0
*
* Insert (key,info) into the heap and return the newly generated HeapNode.
*
*/
public HeapNode insert(int key, String info) { // O(1), lazy insertion, only connecting pointers and adjusting fields.
HeapNode nodeToInsert = new HeapNode(key, info);
fibSize++;
return addNodeToRootList(nodeToInsert);
}
/**
*
* pre: key > 0
*
* adds the root into the heap and return the newly inserted root.
*
*/
public HeapNode addNodeToRootList(HeapNode nodeToInsert) { // O(1) lazy insertion, only connecting pointers and adjusting fields.
nodeToInsert.parent = null; //any root's parent is null
nodeToInsert.mark = false; //any root's mark is false
if (min == null) { // the heap was empty
min = nodeToInsert;
min.next = min;
min.prev = min;
} else { // heap was not empty
nodeToInsert.prev = min;
nodeToInsert.next = min.next; // add the new node after the curr min node
min.next.prev = nodeToInsert;
min.next = nodeToInsert;
if (nodeToInsert.key < min.key) { // update the min pointer if the new key< min.key
min = nodeToInsert;
}
}
//no need to adjust size- the functions calling this one adjust as needed
numOfTrees++;
return nodeToInsert;
}
/**
*
* Return the minimal HeapNode, null if empty.
*
*/
public HeapNode findMin() { // O(1)
return min; // the heap's minimal node
}
/**
*
* Delete the minimal item
*
*/
public void deleteMin() { // O(logn) worst case and amortized
HeapNode currmin = min;
if (min == null) {
// The heap is empty, nothing to delete
return;
}
HeapNode currRoot = deleteroot(currmin); // the function deleteroot removes the root and adds his children to
// the roots' list.
if (currRoot == null) { //the heap is empty
return;
}
int currNumOfTrees = numOfTrees;
HeapNode[] nodesArray = new HeapNode[(int) Math.ceil(Math.log(fibSize + 1) / Math.log((1 + Math.sqrt(5)) / 2))]; // At
// the
// end
// we
// will have a
// non-lazy
// binomial heap
// containing at
// most
// logϕ(n+1)
// trees.
HeapNode tempmin = currRoot;
while (currNumOfTrees > 0) { // consolidating
if (currRoot.key < tempmin.key) // updating the minimum.
{
tempmin = currRoot;
}
HeapNode nextRoot = currRoot.next; // keeping a pointer to the next root.
int currRank = currRoot.rank;
if (nodesArray[currRank] == null) { // no other root with this rank, we can put it there
nodesArray[currRank] = currRoot;
} else {
HeapNode newroot = null;
while (nodesArray[currRank] != null) { // there is already a root with this rank in the heap
HeapNode secondHeap = nodesArray[currRank]; //the other root with the rank currRank
if (secondHeap.key <= currRoot.key) { // secondHeap is smaller/ equal
if (currRoot == tempmin)
newroot = makeChild(currRoot, secondHeap); // currRoot is the min so it needs to be the root
else
newroot = makeChild(secondHeap, currRoot); // secondHeap is the new root of the combined tree
} else {
if (secondHeap == tempmin)
newroot = makeChild(secondHeap, currRoot); // secondheap is the min so it needs to be the root
else
newroot = makeChild(currRoot, secondHeap); // currRoot is the new root of the combined tree
}
// newroot is now the root of the combined trees
nodesArray[currRank] = null; // we are moving on to the next bucket
currRank++;
numOfTrees--; // we combined two trees so num of trees is down by 1
currRoot = newroot; //moving to the next bucket with the new root
}
nodesArray[currRank] = newroot; // eventually when we arrived to an empty bucket we put the new root there.
}
currNumOfTrees--;
currRoot = nextRoot; // moving to the next root.
}
// we will now connect all the the new trees in the buckets
min = tempmin;
HeapNode nodeforloop = min;
for (int i = 0; i < nodesArray.length; i++) {
if (nodesArray[i] == min) { // we started from the min so we'll skit it when we encounter it
continue;
} else {
if (nodesArray[i] != null) { // there is a tree with this rank
nodeforloop.next = nodesArray[i]; // connecting the roots
nodesArray[i].prev = nodeforloop;
nodeforloop = nodeforloop.next;
}
}
}
nodeforloop.next = min; // eventually we'll connect the last and first roots to close the circular list
min.prev = nodeforloop;
}
public HeapNode makeChild(HeapNode father, HeapNode son) { // O(1), linking the father and son only adjusting pointers and fields
if (father.child == null) // there are no kids, linking the child to the parent.
{
father.child = son;
son.parent = father;
son.next = son;
son.prev = son;
} else // there are kids, adding son to the list of childern.
{
son.prev = father.child;
son.next = father.child.next;
father.child.next.prev = son;
father.child.next = son;
son.parent = father;
}
father.rank++;
numOfLinks++;
return father;
}
public HeapNode deleteroot(HeapNode rootToRemove) { // O(d) - d is the number of roots children. removing a root from a list ,only adjusting pointers (O(1) for each kid) and fields
// check if size ==1
if (fibSize == 1) {
min = null;
fibSize--;
numOfTrees--;
return null;
}
HeapNode newpointer = null;
if (numOfTrees == 1)// so for sure there is a child for rootToRemove because fibsize != 1
{
newpointer = rootToRemove.child;
} else {
newpointer = rootToRemove.next; // threre is another tree, so for sure he has a next node.
}
if (rootToRemove != null) {
int currRank = rootToRemove.rank;
HeapNode child = rootToRemove.child; // if currRank == 0, child is null and we won't go into the loop
HeapNode tmp = null;
while (currRank > 0) {// adding all of the to-be-deleted-root's children to the list as well
tmp = child.next;
child.prev = null;
child.next = null;
numOfCuts++;
addNodeToRootList(child);
child = tmp;
currRank--;
}
if (rootToRemove.prev != null) {
rootToRemove.prev.next = rootToRemove.next;
}
if (rootToRemove.next != null) {
rootToRemove.next.prev = rootToRemove.prev;
}
rootToRemove.next = null;
rootToRemove.prev = null;
rootToRemove.child = null;
numOfTrees--;
fibSize--;
return newpointer;
}
return null; // we know it says "dead code" but upon removing it we get an error
}
/**
*
* pre: 0<diff<x.key
*
* Decrease the key of x by diff and fix the heap.
*
*/
public void decreaseKey(HeapNode x, int diff) { // O(n) worst case, O(1) amortized
x.key = x.key - diff;
HeapNode parentOfx = x.parent;
if ((parentOfx != null) && (x.key < parentOfx.key)) { // violating the heap's rule
cut(x, parentOfx);
cascadingCut(parentOfx);
}
if (x.key < min.key) { // adjusting the min if needed
min = x;
}
return;
}
// performs a cut operation on x an his parent
public void cut(HeapNode x, HeapNode parentOfx) { // O(1) adjusting pointers and calling O(1) functions
// removes x from the children lists and decreases the rank of parent
x.prev.next = x.next;
x.next.prev = x.prev;
parentOfx.rank--;
// reset parent child if necessary
if (parentOfx.child == x) {
parentOfx.child = x.next;
}
if (parentOfx.rank == 0) { // 0 after decreasing- meaning x was an only child
parentOfx.child = null;
}
// add x to root list of heap
addNodeToRootList(x);
numOfCuts++;
// set mark to false
x.mark = false;
}
// Performs cascading cut on the given node as given in Cormen
public void cascadingCut(HeapNode y) { // O(n) worst case, O(1) amortized- this is the cost of decrease key
HeapNode parentOfy = y.parent;
// if there is a parent
if (parentOfy != null) {
// if y is unmarked
if (y.mark == false) {
y.mark = true;
} else {
// y is already marked, cut it from his parent
cut(y, parentOfy);
// recursivly continue to check if his parent has already been marked
cascadingCut(parentOfy);
}
}
}
/**
*
* Delete the x from the heap.
*
*/
public void delete(HeapNode x) { //O(n) worst case, O(logn) amortized
if (x == null) {
return;
}
HeapNode parentOfx = x.parent;
if (x == min) {
deleteMin();
}
else {
if (parentOfx != null) {
cut(x, parentOfx);
cascadingCut(parentOfx);
}
deleteroot(x);
}
return;
}
/**
*
* Return the total number of links.
*
*/
public int totalLinks() { // O(1)
return numOfLinks;
}
/**
*
* Return the total number of cuts.
*
*/
public int totalCuts() { // O(1)
return numOfCuts;
}
/**
*
* Meld the heap with heap2
*
*/
public void meld(FibonacciHeap heap2) { // O(1) only adjusting pointers and fields
if (fibSize == 0 || heap2.fibSize == 0) {
if (fibSize == 0) {
min = heap2.findMin();
heap2.min = null;
}
} else {
HeapNode min2 = heap2.findMin();
HeapNode lastheap2 = min2.prev;
HeapNode nextnode = min.next;
min.next = min2;
min2.prev = min;
lastheap2.next = nextnode;
nextnode.prev = lastheap2;
if (min2.key < min.key) { // update min if needed
min = min2;
}
}
// update heap fields
numOfCuts = numOfCuts + heap2.numOfCuts;
numOfLinks = numOfLinks + heap2.numOfLinks;
numOfTrees = numOfTrees + heap2.numOfTrees;
fibSize = fibSize + heap2.fibSize;
return;
}
/**
*
* Return the number of elements in the heap
*
*/
public int size() {
return fibSize;
}
/**
*
* Return the number of trees in the heap.
*
*/
public int numTrees() {
return numOfTrees;
}
/**
* Class implementing a node in a Fibonacci Heap.
*
*/
public static class HeapNode {
public int key;
public String info;
public HeapNode child;
public HeapNode next;
public HeapNode prev;
public HeapNode parent;
public int rank;
public boolean mark;
public HeapNode(int key, String info) {
this.key = key;
this.info = info;
}
}}