org.siebengeisslein.util
Class LongHeap

java.lang.Object
  org.siebengeisslein.util.LongHeap

public class LongHeap
extends java.lang.Object

This class implements a heap that contains Comparables. It is base on an implementation from Robert Sedgewicks book "Algorithms". It has to be assured, when using the heap, that the comparTo() method of all objects are compatible and do not throw a ClassNotFoundException, when compared to aach other. In a heap is it possible to add elemnts to this heap, and to remove the first element (which is bigger than all other elements). This implementation provides guaranteed log(n) time cost for both operations.

Author:

Niklas Mehner

Constructor Summary

LongHeap()
Creates a new heap with a default size.

LongHeap(int initialSize)
Creates a new heap with a given initial size.

Method Summary

void	add(long value) Add a new entry to the heap.
java.lang.Object	clone()
boolean	contains(long value)
boolean	isEmpty() Return wether this heap is empty.
void	read(java.io.RandomAccessFile file)
long	removeFirst() Returns the biggest entry of the heap and removes it.
int	size() Return the size of the heap.
void	write(java.io.RandomAccessFile file)

Methods inherited from class java.lang.Object

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

Constructor Detail

LongHeap

public LongHeap()

Creates a new heap with a default size.

LongHeap

public LongHeap(int initialSize)

Creates a new heap with a given initial size. When more than initialSize elements are added, the size of the internal storage structure is doubled.

Parameters:

initialSize - Initial size of the heap (>0)

Method Detail

contains

public boolean contains(long value)

add

public void add(long value)

Add a new entry to the heap.

Parameters:

obj - New Entry. This has to be comparable to all other entries in the heap and may not be null.

removeFirst

public long removeFirst()

Returns the biggest entry of the heap and removes it. A EmptyHeapException is thrown, if the heap is empty.

Returns:

The biggest entry of the heap.

size

public int size()

Return the size of the heap.

Returns:

Size of the heap.

isEmpty

public boolean isEmpty()

Return wether this heap is empty.

Returns:

True, if the heap is empty.

write

public void write(java.io.RandomAccessFile file)
           throws java.io.IOException

Throws:

java.io.IOException

read

public void read(java.io.RandomAccessFile file)
          throws java.io.IOException

Throws:

java.io.IOException

clone

public java.lang.Object clone()

Overrides:

clone in class java.lang.Object