com.cometway.util
Class BinaryHeap

java.lang.Object
  com.cometway.util.BinaryHeap

All Implemented Interfaces:

IHeap

public class BinaryHeap
extends java.lang.Object
implements IHeap

BinaryHeap is a mostly vanilla implementation of the CLR binary heap (albeit an object-oriented implementation), with the addition of a Hashtable mapping IHeapItems to their respective indices in the heap Vector. this allows for (nearly) constant time deletion of arbitrary IHeapItems at the cost of a bit of hashing (ohhh, sweet hash...)

Constructor Summary

BinaryHeap()
UNICONSTRUCTOR

Method Summary

boolean	delete(IHeapItem deleteItem) delete
IHeapItem	deleteMin() deleteMin: method removes and returns the minimum IHeapItem in this heap
boolean	empty() empty: method returns true if this heap contains no elements and false otherwise.
IHeapItem	findMin() findMin: method returns the minimum IHeapItem in this heap
boolean	insert(IHeapItem newItem) insert: method adds a IHeapItem to this heap
boolean	isEmpty() isEmpty: method returns true if this heap contains no elements and false otherwise
void	print()
int	size() size: method returns the number of elements in this heap

Methods inherited from class java.lang.Object

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

Constructor Detail

BinaryHeap

public BinaryHeap()

UNICONSTRUCTOR

Method Detail

insert

public boolean insert(IHeapItem newItem)

insert: method adds a IHeapItem to this heap

Specified by:

insert in interface IHeap

delete

public boolean delete(IHeapItem deleteItem)

delete

Specified by:

delete in interface IHeap

findMin

public IHeapItem findMin()

findMin: method returns the minimum IHeapItem in this heap

Specified by:

findMin in interface IHeap

deleteMin

public IHeapItem deleteMin()

deleteMin: method removes and returns the minimum IHeapItem in this heap

Specified by:

deleteMin in interface IHeap

isEmpty

public boolean isEmpty()

isEmpty: method returns true if this heap contains no elements and false otherwise

Specified by:

isEmpty in interface IHeap

empty

public boolean empty()

empty: method returns true if this heap contains no elements and false otherwise. note: this version of isEmpty is retained for compatibility with old code

size

public int size()

size: method returns the number of elements in this heap

Specified by:

size in interface IHeap

print

public void print()