|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apache.avalon.cornerstone.blocks.scheduler.BinaryHeap
public final class BinaryHeap
BinaryHeap implementation of priority queue. The heap is either a minimum or maximum heap as determined by parameters passed to constructor.
Nested Class Summary | |
---|---|
private static class |
BinaryHeap.MaxComparator
|
private static class |
BinaryHeap.MinComparator
|
Field Summary | |
---|---|
private static int |
DEFAULT_CAPACITY
|
private static java.util.Comparator |
DEFAULT_COMPARATOR
|
private java.util.Comparator |
m_comparator
|
private java.lang.Object[] |
m_elements
|
private int |
m_size
|
static java.util.Comparator |
MAX_COMPARATOR
Comparator used to instantiate a max heap - assumes contents implement the Comparable interface. |
static java.util.Comparator |
MIN_COMPARATOR
Comparator used to instantiate a min heap - assumes contents implement the Comparable interface. |
Constructor Summary | |
---|---|
BinaryHeap()
Instantiates a new min binary heap with the default initial capacity. |
|
BinaryHeap(boolean isMinHeap)
Create a binary heap of Comparables. |
|
BinaryHeap(java.util.Comparator comparator)
Instantiates a new binary heap with the default initial capacity and ordered using the given Comparator. |
|
BinaryHeap(int capacity)
Instantiates a new min binary heap with the given initial capacity. |
|
BinaryHeap(int capacity,
boolean isMinHeap)
Create a binary heap of Comparables. |
|
BinaryHeap(int capacity,
java.util.Comparator comparator)
Instantiates a new binary heap with the given initial capacity and ordered using the given Comparator. |
Method Summary | |
---|---|
void |
clear()
Clear all elements from queue. |
private void |
grow()
Grows the heap by a factor of 2. |
void |
insert(java.lang.Object element)
Insert an element into queue. |
boolean |
isEmpty()
Test if queue is empty. |
boolean |
isFull()
Test if queue is full. |
java.lang.Object |
peek()
Return element on top of heap but don't remove it. |
private void |
percolateDownHeap(int index)
Percolate element down heap from top. |
private void |
percolateUpHeap(java.lang.Object element)
Percolate element up heap from bottom. |
java.lang.Object |
pop()
Return element on top of heap and remove it. |
int |
size()
Returns the number of elements currently on the heap. |
java.lang.String |
toString()
Create a string representing heap and all elements in heap. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
---|
public static final java.util.Comparator MIN_COMPARATOR
public static final java.util.Comparator MAX_COMPARATOR
private static final int DEFAULT_CAPACITY
private static final java.util.Comparator DEFAULT_COMPARATOR
private int m_size
private java.lang.Object[] m_elements
private java.util.Comparator m_comparator
Constructor Detail |
---|
public BinaryHeap()
public BinaryHeap(int capacity)
capacity
- the size of the heappublic BinaryHeap(java.util.Comparator comparator)
comparator
- to order the contents of the heappublic BinaryHeap(int capacity, java.util.Comparator comparator)
capacity
- the size of the heapcomparator
- to order the contents of the heappublic BinaryHeap(boolean isMinHeap)
isMinHeap
- true to make it a minimum heap, false to make it a max heappublic BinaryHeap(int capacity, boolean isMinHeap)
capacity
- the size of the heapisMinHeap
- true to make it a minimum heap, false to make it a max heapMethod Detail |
---|
public void clear()
clear
in interface PriorityQueue
public boolean isEmpty()
isEmpty
in interface PriorityQueue
public boolean isFull()
public int size()
public void insert(java.lang.Object element)
insert
in interface PriorityQueue
element
- the element to be insertedpublic java.lang.Object peek() throws java.util.NoSuchElementException
peek
in interface PriorityQueue
java.util.NoSuchElementException
- if isEmpty() == truepublic java.lang.Object pop() throws java.util.NoSuchElementException
pop
in interface PriorityQueue
java.util.NoSuchElementException
- if isEmpty() == trueprivate void percolateDownHeap(int index)
index
- the index of elementprivate void percolateUpHeap(java.lang.Object element)
element
- the elementprivate void grow()
public java.lang.String toString()
toString
in class java.lang.Object
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |