xxl.collections
Class Heap

java.lang.Object
  |
  +--xxl.collections.AbstractQueue
        |
        +--xxl.collections.Heap

Direct Known Subclasses:

DynamicHeap

public class Heap

extends AbstractQueue

The heap datastructure.

Field Summary

protected java.lang.Object[]	array The array used for the internal representation of the data.
protected java.util.Comparator	comparator The Comparator used to compare elements in the heap.
static Function	FACTORY_METHOD A factory method to create a new Heap.
protected int	last The last element in the heap.

Fields inherited from class xxl.collections.AbstractQueue

FACTORY_METHOD

Constructor Summary

Heap(int size)
Creates an empty Heap.

Heap(int size, java.util.Comparator comparator)
Creates an empty Heap.

Heap(java.lang.Object[] array)
Creates a Heap for a given Array in O(n) time.

Heap(java.lang.Object[] array, java.util.Comparator comparator)
Creates a Heap for a given Array in O(n) time.

Heap(java.lang.Object[] array, int size)
Creates a Heap for a given Array in O(n) time.

Heap(java.lang.Object[] array, int size, java.util.Comparator comparator)
Creates a Heap for a given Array in O(n) time.

Method Summary

protected void	bubbleUp(java.lang.Object object, int i)
void	clear() Removes all elements from the heap.
protected void	heapify() Computes the heap for a given Array in O(n) time.
void	insert(java.lang.Object object) Inserts an Object into the heap.
void	insertAll(java.util.Iterator objects) Inserts all elements of a given Iterator into the heap.
java.lang.Object	next() Returns the next element in the iteration.
java.lang.Object	peek() Shows the next element in the iteration without removing it.
java.lang.Object	replace(java.lang.Object object) Inserts a given object and returns this.next().
protected int	sinkIn(int i)
int	size() Returns the size of the heap.
boolean	supportsPeek() Returns true if the peek operation is supported by this PeekIterator.

Methods inherited from class xxl.collections.AbstractQueue

close, hasNext, remove, replaceAll

Methods inherited from class java.lang.Object

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

Field Detail

FACTORY_METHOD

public static final Function FACTORY_METHOD

A factory method to create a new Heap. It may be invoked with or without a given array.

array

protected java.lang.Object[] array

The array used for the internal representation of the data.

last

protected int last

The last element in the heap.

comparator

protected java.util.Comparator comparator

The Comparator used to compare elements in the heap.

Constructor Detail

Heap

public Heap(java.lang.Object[] array,
            int size,
            java.util.Comparator comparator)

Creates a Heap for a given Array in O(n) time.

Parameters:

array - the array for which the heap is to be created

size - the size of the heap

the - Comparator used to compare elements in the heap

Heap

public Heap(java.lang.Object[] array)

Creates a Heap for a given Array in O(n) time.

Parameters:

array - the array for which the heap is to be created

Heap

public Heap(java.lang.Object[] array,
            int size)

Creates a Heap for a given Array in O(n) time.

Parameters:

array - the array for which the heap is to be created

size - the size of the heap

Heap

public Heap(java.lang.Object[] array,
            java.util.Comparator comparator)

Creates a Heap for a given Array in O(n) time.

Parameters:

array - the array for which the heap is to be created

the - Comparator used to compare elements in the heap

Heap

public Heap(int size,
            java.util.Comparator comparator)

Creates an empty Heap.

Parameters:

size - the maximum size of the heap

the - Comparator used to compare elements in the heap

Heap

public Heap(int size)

Creates an empty Heap.

Parameters:

size - the maximum size of the heap

Method Detail

heapify

protected void heapify()

Computes the heap for a given Array in O(n) time.

bubbleUp

protected void bubbleUp(java.lang.Object object,
                        int i)

sinkIn

protected int sinkIn(int i)

clear

public void clear()

Removes all elements from the heap.

Overrides:

clear in class AbstractQueue

size

public int size()

Returns the size of the heap.

Overrides:

size in class AbstractQueue

insert

public void insert(java.lang.Object object)

Inserts an Object into the heap.

Overrides:

insert in class AbstractQueue

insertAll

public void insertAll(java.util.Iterator objects)

Inserts all elements of a given Iterator into the heap.

Parameters:

objects - an Iterator of Objects

Overrides:

insertAll in class AbstractQueue

peek

public java.lang.Object peek()
                      throws java.util.NoSuchElementException

Shows the next element in the iteration without removing it.

Returns:

the next element in the iteration.

Throws:

java.util.NoSuchElementException - iteration has no more elements.

java.lang.UnsupportedOperationException - if the peek operation is not supported by this PeekIterator.

Overrides:

peek in class AbstractQueue

next

public java.lang.Object next()
                      throws java.util.NoSuchElementException

Returns the next element in the iteration.

Returns:

the next element in the iteration.

Throws:

java.util.NoSuchElementException - iteration has no more elements.

Overrides:

next in class AbstractQueue

replace

public java.lang.Object replace(java.lang.Object object)
                         throws java.util.NoSuchElementException

Inserts a given object and returns this.next().

Overrides:

replace in class AbstractQueue

supportsPeek

public boolean supportsPeek()

Returns true if the peek operation is supported by this PeekIterator.

Returns:

true if the peek operation is supported by this PeekIterator

Overrides:

supportsPeek in class AbstractQueue