|
||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--org.apache.commons.collections.BinaryHeap
Binary heap implementation of PriorityQueue
.
Field Summary | |
protected static int |
DEFAULT_CAPACITY
|
protected Object[] |
m_elements
|
protected boolean |
m_isMinHeap
|
protected int |
m_size
|
Constructor Summary | |
BinaryHeap()
Create a new minimum binary heap. |
|
BinaryHeap(boolean isMinHeap)
Create a new minimum or maximum binary heap |
|
BinaryHeap(boolean isMinHeap,
Comparator comparator)
|
|
BinaryHeap(Comparator comparator)
|
|
BinaryHeap(int capacity)
Create a new minimum binary heap with the specified initial capacity. |
|
BinaryHeap(int capacity,
boolean isMinHeap)
Create a new minimum or maximum binary heap with the specified initial capacity. |
|
BinaryHeap(int capacity,
boolean isMinHeap,
Comparator comparator)
|
|
BinaryHeap(int capacity,
Comparator comparator)
|
Method Summary | |
void |
clear()
Clear all elements from queue. |
protected void |
grow()
Increase the size of the heap to support additional elements |
void |
insert(Object element)
Insert an element into queue. |
boolean |
isEmpty()
Test if queue is empty. |
boolean |
isFull()
Test if queue is full. |
Object |
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(Object element)
Percolate element up heap from bottom. |
protected void |
percolateUpMinHeap(Object element)
Percolate element up heap from bottom. |
Object |
pop()
Return element on top of heap and remove it. |
String |
toString()
|
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
protected static final int DEFAULT_CAPACITY
protected Object[] m_elements
protected boolean m_isMinHeap
protected int m_size
Constructor Detail |
public BinaryHeap()
public BinaryHeap(boolean isMinHeap)
isMinHeap
- if true
the heap is created as a
minimum heap; otherwise, the heap is created as a maximum heap.public BinaryHeap(boolean isMinHeap, Comparator comparator)
public BinaryHeap(Comparator comparator)
public BinaryHeap(int capacity)
capacity
- the initial capacity for the heap. This value must
be greater than zero.IllegalArgumentException
- if capacity
is <= 0
public BinaryHeap(int capacity, boolean isMinHeap)
capacity
- the initial capacity for the heap. This value must
be greater than zero.isMinHeap
- if true
the heap is created as a
minimum heap; otherwise, the heap is created as a maximum heap.IllegalArgumentException
- if capacity
is <= 0
public BinaryHeap(int capacity, boolean isMinHeap, Comparator comparator)
public BinaryHeap(int capacity, Comparator comparator)
Method Detail |
public void clear()
clear
in interface PriorityQueue
protected void grow()
public void insert(Object element)
insert
in interface PriorityQueue
element
- the element to be insertedpublic boolean isEmpty()
isEmpty
in interface PriorityQueue
true
if queue is empty; false
otherwise.public boolean isFull()
true
if queue is full; false
otherwise.public Object peek() throws NoSuchElementException
peek
in interface PriorityQueue
NoSuchElementException
- if isEmpty() == true
protected void percolateDownMaxHeap(int index)
index
- the index of the elementprotected void percolateDownMinHeap(int index)
index
- the index for the elementprotected void percolateUpMaxHeap(Object element)
element
- the elementprotected void percolateUpMinHeap(Object element)
element
- the elementpublic Object pop() throws NoSuchElementException
pop
in interface PriorityQueue
NoSuchElementException
- if isEmpty() == true
public String toString()
toString
in class Object
|
||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |