org.jwarp.util
Class BinaryHeap

java.lang.Object
  |
  +--org.jwarp.util.BinaryHeap

All Implemented Interfaces:

IPriorityQueue

public final class BinaryHeap

extends java.lang.Object

implements IPriorityQueue

Iterface for priority queues. This interface does not dictate whether it is min or max heap.

Author:

Anatole Tresch

Field Summary

protected static int	DEFAULT_CAPACITY The default capacity
protected java.lang.Comparable[]	m_elements The current elements
protected boolean	m_isMinHeap Is the heap a minimal heap
protected int	m_size The current size

Constructor Summary

BinaryHeap()
Creates a new binary heap.

BinaryHeap(boolean isMinHeap)
Creates a new binary heap telling it to be a minimal heap or not.

BinaryHeap(int capacity)
Creates a new binary heap with the given capacity.

BinaryHeap(int capacity, boolean isMinHeap)
Creates a new binary heap telling it to be a minimal heap or not and setting its start capacity.

Method Summary

void	clear() Clear all elements from queue.
protected void	grow() Grow the heap
void	insert(java.lang.Comparable element) Insert an element into queue.
boolean	isEmpty() Test if queue is empty.
boolean	isFull() Test if queue is full.
java.lang.Comparable	peek() Return element on top of heap but don't remove it.
protected void	percolateDownMaxHeap(int index) Percolate element down heap from top.
protected void	percolateDownMinHeap(int index) Percolate element down heap from top.
protected void	percolateUpMaxHeap(java.lang.Comparable element) Percolate element up heap from bottom.
protected void	percolateUpMinHeap(java.lang.Comparable element) Percolate element up heap from bottom.
java.lang.Comparable	pop() Return element on top of heap and remove it.
java.lang.String	toString() Construct a string represntation.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_CAPACITY

protected static final int DEFAULT_CAPACITY

The default capacity

m_size

protected int m_size

The current size

m_elements

protected java.lang.Comparable[] m_elements

The current elements

m_isMinHeap

protected boolean m_isMinHeap

Is the heap a minimal heap

Constructor Detail

BinaryHeap

public BinaryHeap()

Creates a new binary heap.

BinaryHeap

public BinaryHeap(int capacity)

Creates a new binary heap with the given capacity.

Parameters:

capacity - The capacity

BinaryHeap

public BinaryHeap(boolean isMinHeap)

Creates a new binary heap telling it to be a minimal heap or not.

Parameters:

isMinHeap - Is the heap minimal or not

BinaryHeap

public BinaryHeap(int capacity,
                  boolean isMinHeap)

Creates a new binary heap telling it to be a minimal heap or not and setting its start capacity.

Parameters:

capacity - The capacity

isMinHeap - Is the heap minimal or not

Method Detail

clear

public void clear()

Clear all elements from queue.

Specified by:

clear in interface IPriorityQueue

isEmpty

public boolean isEmpty()

Test if queue is empty.

Specified by:

isEmpty in interface IPriorityQueue

Returns:

true if queue is empty else false.

isFull

public boolean isFull()

Test if queue is full.

Returns:

true if queue is full else false.

insert

public void insert(java.lang.Comparable element)

Insert an element into queue.

Specified by:

insert in interface IPriorityQueue

Parameters:

element - the element to be inserted

peek

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

Return element on top of heap but don't remove it.

Specified by:

peek in interface IPriorityQueue

Returns:

the element at top of heap

Throws:

java.util.NoSuchElementException - if isEmpty() == true

pop

public java.lang.Comparable pop()
                         throws java.util.NoSuchElementException

Return element on top of heap and remove it.

Specified by:

pop in interface IPriorityQueue

Returns:

the element at top of heap

Throws:

java.util.NoSuchElementException - if isEmpty() == true

percolateDownMinHeap

protected void percolateDownMinHeap(int index)

Percolate element down heap from top. Assume it is a maximum heap.

Parameters:

element - the element

percolateDownMaxHeap

protected void percolateDownMaxHeap(int index)

Percolate element down heap from top. Assume it is a maximum heap.

Parameters:

element - the element

percolateUpMinHeap

protected void percolateUpMinHeap(java.lang.Comparable element)

Percolate element up heap from bottom. Assume it is a maximum heap.

Parameters:

element - the element

percolateUpMaxHeap

protected void percolateUpMaxHeap(java.lang.Comparable element)

Percolate element up heap from bottom. Assume it is a maximum heap.

Parameters:

element - the element

grow

protected void grow()

Grow the heap

toString

public java.lang.String toString()

Construct a string represntation.

Overrides:

toString in class java.lang.Object

Returns:

The representation string