org.jboss.util

Class Heap

java.lang.Object

org.jboss.util.Heap

public class Heap
extends java.lang.Object

Data structure that mantains data in a ordered binary tree; each node is greater (smaller) or equal than its 2 sub-nodes, for all the hierarchy.

Elements of this data structure should either implement Comparable, or a Comparator should be given as argument to the constructor.

Version:

$Revision$

Field Summary

Fields

Modifier and Type	Field and Description
private java.util.Comparator	m_comparator
private int	m_count
private java.lang.Object[]	m_nodes

Constructor Summary

Constructors

Constructor and Description
Heap() Creates a new Heap whose elements inserted implement the Comparable interface.
Heap(java.util.Comparator comparator) Creates a new Heap whose elements are compared using the given Comparator.

Method Summary

Modifier and Type	Method and Description
void	clear() Empties this heap
protected int	compare(java.lang.Object o1, java.lang.Object o2)
java.lang.Object	extract() Removes and returns the least element of this heap.
void	insert(java.lang.Object obj) Inserts the given element in this heap.
protected int	left(int index)
protected int	parent(int index)
java.lang.Object	peek()
protected int	right(int index)

Methods inherited from class java.lang.Object

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

Field Detail

m_comparator

private java.util.Comparator m_comparator

m_count

private int m_count

m_nodes

private java.lang.Object[] m_nodes

Constructor Detail

Heap

public Heap()

Creates a new Heap whose elements inserted implement the Comparable interface.

Heap

public Heap(java.util.Comparator comparator)

Creates a new Heap whose elements are compared using the given Comparator.

Parameters:

comparator -

Method Detail

insert

public void insert(java.lang.Object obj)

Inserts the given element in this heap.

Parameters:

obj -

See Also:

extract()

extract

public java.lang.Object extract()

Removes and returns the least element of this heap.

Returns:

the extracted object

See Also:

insert(java.lang.Object), peek()

peek

public java.lang.Object peek()

Returns:

without removing it, the least element of this heap.

See Also:

extract()

clear

public void clear()

Empties this heap

compare

protected int compare(java.lang.Object o1,
                      java.lang.Object o2)

parent

protected int parent(int index)

Parameters:

index -

Returns:

the parent index of index.

left

protected int left(int index)

Parameters:

index -

Returns:

the left child index of index.

right

protected int right(int index)

Parameters:

index -

Returns:

the right child index of index.