net.walend.collection
Class FibIntHeap

java.lang.Object
  |
  +--net.walend.collection.FibIntHeap

All Implemented Interfaces:

IntHeap

public class FibIntHeap

extends java.lang.Object

implements IntHeap

FibIntHeap is an IntHeap built on top of a Fibinocci heap.

Author:

David Walend dfw1@cornell.edu

Nested Class Summary

private class

FibIntHeap.ChildIterator

Field Summary

private int	size
private IntHeapMember	top

Constructor Summary

FibIntHeap()

Method Summary

private void	cascadingCut(IntHeapMember y)
void	changeKey(int key, IntHeapMember fibNode)
private void	checkKeyValue(int key)
private void	checkTop()
private void	consolidate()
private void	cut(IntHeapMember x, IntHeapMember y) Removes x from the child list of y.
private void	decreaseKey(int key, IntHeapMember fibNode)
IntHeapMember	getMin()
int	getMinKey()
void	insert(int key, IntHeapMember fibNode)
boolean	isEmpty()
protected java.util.Iterator	iterator()
private void	link(IntHeapMember y, IntHeapMember x) Make y a child of x.
void	remove(IntHeapMember fibNode)
int	size()
IntHeapMember	takeMin()
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

top

private IntHeapMember top

size

private int size

Constructor Detail

FibIntHeap

public FibIntHeap()

Method Detail

cascadingCut

private void cascadingCut(IntHeapMember y)

consolidate

private void consolidate()

cut

private void cut(IntHeapMember x,
                 IntHeapMember y)

Removes x from the child list of y.

link

private void link(IntHeapMember y,
                  IntHeapMember x)

Make y a child of x.

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface IntHeap

checkKeyValue

private void checkKeyValue(int key)

checkTop

private void checkTop()

insert

public void insert(int key,
                   IntHeapMember fibNode)

Specified by:

insert in interface IntHeap

getMin

public IntHeapMember getMin()

Specified by:

getMin in interface IntHeap

getMinKey

public int getMinKey()

Specified by:

getMinKey in interface IntHeap

takeMin

public IntHeapMember takeMin()

Specified by:

takeMin in interface IntHeap

decreaseKey

private void decreaseKey(int key,
                         IntHeapMember fibNode)

changeKey

public void changeKey(int key,
                      IntHeapMember fibNode)

Specified by:

changeKey in interface IntHeap

remove

public void remove(IntHeapMember fibNode)

Specified by:

remove in interface IntHeap

size

public int size()

Specified by:

size in interface IntHeap

iterator

protected java.util.Iterator iterator()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object