nenok.lc.constr.vvll
Class Heap<C extends Comparable>

java.lang.Object
  extended by nenok.lc.constr.vvll.Heap<C>
Type Parameters:
C - Class implementing the Comparable insterface.
All Implemented Interfaces:
Iterable<C>

public class Heap<C extends Comparable>
extends Object
implements Iterable<C>

This class offers a generic implementation of a binary heap data structure. All elements need to implements the Comparable interface to guarantee that they can be ordered to reconstruct the heap structure. This heap implementation asserts that the smallest elements is always on top of the heap and removed first. To determine the smallest element, the operation compareTo(Object o) from Comparable is called.

Version:
1.1
Author:
Marc Pouly

Constructor Summary
Heap()
          Constructor: Creates a new empty heap.
Heap(Collection<C> c)
          Constructor: Creates a heap from a given collection of Comparable objects.
 
Method Summary
 void add(C value)
          Adds a single element to the heap.
 void add(Collection<C> c)
          Adds a collection of elements to the heap.
 int getPosition(C c)
          Returns the index of the given object in the heap.
 Iterator<C> iterator()
          The iterator of the collection interface.
 C remove()
          Removes the root (= smallest element) of the heap.
 int size()
          Returns the number of elements contained in the heap.
 void update(int index)
          Updates the heap, if the given node has changed.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Heap

public Heap()
Constructor: Creates a new empty heap.


Heap

public Heap(Collection<C> c)
Constructor: Creates a heap from a given collection of Comparable objects.

Parameters:
c - The collection of heap elements.
Method Detail

add

public void add(C value)
Adds a single element to the heap.

Parameters:
value - The element to add.

add

public void add(Collection<C> c)
Adds a collection of elements to the heap.

Parameters:
c - The collection of elements to add.

remove

public C remove()
Removes the root (= smallest element) of the heap.

Returns:
The root of the heap.

iterator

public Iterator<C> iterator()
The iterator of the collection interface.

Specified by:
iterator in interface Iterable<C extends Comparable>
Returns:
The heap's iterator.

size

public int size()
Returns the number of elements contained in the heap.

Returns:
The heap's size.

update

public void update(int index)
Updates the heap, if the given node has changed.

Parameters:
index - The node to update.

getPosition

public int getPosition(C c)
Returns the index of the given object in the heap.

Parameters:
c - The object to search.
Returns:
The object's position.