JBoss Common Classes 2.2.17.GA

org.jboss.util
Class Heap

java.lang.Object
  extended by org.jboss.util.Heap

public class Heap
extends 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: 2787 $
Author:
Simone Bordet

Constructor Summary
Heap()
          Creates a new Heap whose elements inserted implement the Comparable interface.
Heap(Comparator comparator)
          Creates a new Heap whose elements are compared using the given Comparator.
 
Method Summary
 void clear()
          Empties this heap
protected  int compare(Object o1, Object o2)
           
 Object extract()
          Removes and returns the least element of this heap.
 void insert(Object obj)
          Inserts the given element in this heap.
protected  int left(int index)
           
protected  int parent(int index)
           
 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
 

Constructor Detail

Heap

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


Heap

public Heap(Comparator comparator)
Creates a new Heap whose elements are compared using the given Comparator.

Parameters:
comparator -
Method Detail

insert

public void insert(Object obj)
Inserts the given element in this heap.

Parameters:
obj -
See Also:
extract()

extract

public Object extract()
Removes and returns the least element of this heap.

Returns:
the extracted object
See Also:
insert(java.lang.Object), peek()

peek

public 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(Object o1,
                      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.

JBoss Common Classes 2.2.17.GA

Copyright © 2011 JBoss, a division of Red Hat, Inc.. All Rights Reserved.