Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2020
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.35 KB | None | 0 0
  1.     public static int[] kMin(FibonacciHeap H, int k)
  2.     {
  3.         int[] minimums = new int[k];
  4.         int minIndex = 0;
  5.         // add root to new heap
  6.         FibonacciHeap minsHeap = new FibonacciHeap();
  7.         ArrayList<HeapNode> nodes = new ArrayList<>();
  8.         minsHeap.insert(H.getFirst().getKey());
  9.         nodes.add(H.getFirst());
  10.  
  11.         while (minIndex < k) {
  12.             minimums[minIndex] = minsHeap.findMin().getKey();
  13.             minIndex++;
  14.             HeapNode minNode = null;
  15.             for (HeapNode node : nodes) { // find the pointer of the node in the original tree
  16.                 if (node.getKey() == minsHeap.findMin().getKey()) {
  17.                     minNode = node;
  18.                     break;
  19.                 }
  20.             }
  21.  
  22.             // add new minimum's children to the heap and the pointer list
  23.             HeapNode minNodeFirstChild = minNode.getChild();
  24.             if (minNodeFirstChild != null) {
  25.                 HeapNode childNode = minNodeFirstChild;
  26.                 do {
  27.                     minsHeap.insert(childNode.getKey());
  28.                     nodes.add(childNode);
  29.                     childNode = childNode.getNext();
  30.                 }
  31.                 while (childNode.getKey() != minNodeFirstChild.getKey());
  32.             }
  33.             minsHeap.deleteMin();
  34.         }
  35.         return minimums;
  36.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement