Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public static int[] kMin(FibonacciHeap H, int k)
- {
- int[] minimums = new int[k];
- int minIndex = 0;
- // add root to new heap
- FibonacciHeap minsHeap = new FibonacciHeap();
- ArrayList<HeapNode> nodes = new ArrayList<>();
- minsHeap.insert(H.getFirst().getKey());
- nodes.add(H.getFirst());
- while (minIndex < k) {
- minimums[minIndex] = minsHeap.findMin().getKey();
- minIndex++;
- HeapNode minNode = null;
- for (HeapNode node : nodes) { // find the pointer of the node in the original tree
- if (node.getKey() == minsHeap.findMin().getKey()) {
- minNode = node;
- break;
- }
- }
- // add new minimum's children to the heap and the pointer list
- HeapNode minNodeFirstChild = minNode.getChild();
- if (minNodeFirstChild != null) {
- HeapNode childNode = minNodeFirstChild;
- do {
- minsHeap.insert(childNode.getKey());
- nodes.add(childNode);
- childNode = childNode.getNext();
- }
- while (childNode.getKey() != minNodeFirstChild.getKey());
- }
- minsHeap.deleteMin();
- }
- return minimums;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement