Package 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 Description private java.util.Comparator
m_comparator
private int
m_count
private java.lang.Object[]
m_nodes
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
clear()
Empties this heapprotected 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)
-
-
-
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
.
-
-