|
||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--java.util.AbstractCollection | +--org.apache.commons.collections.BinaryHeap
Binary heap implementation of PriorityQueue
and Buffer
.
The removal order of a binary heap is based on either the natural sort
order of its elements or a specified Comparator
. The
remove()
method always returns the first element as determined
by the sort order. (The isMinHeap
flag in the constructors
can be used to reverse the sort order, in which case remove()
will always remove the last element.) The removal order is
not the same as the order of iteration; elements are
returned by the iterator in no particular order.
The add(Object)
and remove()
operations perform
in logarithmic time. The get()
operation performs in constant
time. All other operations perform in linear time or worse.
Note that this implementation is not synchronized. Use
BufferUtils.synchronizedBuffer(Buffer)
to provide
synchronized access to a BinaryHeap
:
Buffer heap = BufferUtils.synchronizedBuffer(new BinaryHeap());
Constructor Summary | |
BinaryHeap()
Constructs a new minimum binary heap. |
|
BinaryHeap(boolean isMinHeap)
Constructs a new minimum or maximum binary heap |
|
BinaryHeap(boolean isMinHeap,
Comparator comparator)
Constructs a new BinaryHeap . |
|
BinaryHeap(Comparator comparator)
Constructs a new BinaryHeap that will use the given
comparator to order its elements. |
|
BinaryHeap(int capacity)
Constructs a new minimum binary heap with the specified initial capacity. |
|
BinaryHeap(int capacity,
boolean isMinHeap)
Constructs a new minimum or maximum binary heap with the specified initial capacity. |
|
BinaryHeap(int capacity,
boolean isMinHeap,
Comparator comparator)
Constructs a new BinaryHeap . |
|
BinaryHeap(int capacity,
Comparator comparator)
Constructs a new BinaryHeap . |
Method Summary | |
boolean |
add(Object object)
Adds an object to this heap. |
void |
clear()
Clears all elements from queue. |
Object |
get()
Returns the priority element. |
protected void |
grow()
Increases the size of the heap to support additional elements |
void |
insert(Object element)
Inserts an element into queue. |
boolean |
isEmpty()
Tests if queue is empty. |
boolean |
isFull()
Tests if queue is full. |
Iterator |
iterator()
Returns an iterator over this heap's elements. |
Object |
peek()
Returns the element on top of heap but don't remove it. |
protected void |
percolateDownMaxHeap(int index)
Percolates element down heap from top. |
protected void |
percolateDownMinHeap(int index)
Percolates element down heap from top. |
protected void |
percolateUpMaxHeap(Object element)
Percolates element up heap from bottom. |
protected void |
percolateUpMinHeap(Object element)
Percolates element up heap from bottom. |
Object |
pop()
Returns the element on top of heap and remove it. |
Object |
remove()
Removes the priority element. |
int |
size()
Returns the number of elements in this heap. |
String |
toString()
Returns a string representation of this heap. |
Methods inherited from class java.util.AbstractCollection |
addAll,
contains,
containsAll,
remove,
removeAll,
retainAll,
toArray,
toArray |
Methods inherited from class java.lang.Object |
clone,
equals,
finalize,
getClass,
hashCode,
notify,
notifyAll,
wait,
wait,
wait |
Constructor Detail |
public BinaryHeap()
public BinaryHeap(Comparator comparator)
BinaryHeap
that will use the given
comparator to order its elements.comparator
- the comparator used to order the elements, null
means use natural orderpublic BinaryHeap(int capacity)
capacity
- The initial capacity for the heap. This value must
be greater than zero.capacity
is <= 0
public BinaryHeap(int capacity, Comparator comparator)
BinaryHeap
.capacity
- the initial capacity for the heapcomparator
- the comparator used to order the elements, null
means use natural ordercapacity
is <= 0
public BinaryHeap(boolean isMinHeap)
isMinHeap
- if true
the heap is created as a
minimum heap; otherwise, the heap is created as a maximum heappublic BinaryHeap(boolean isMinHeap, Comparator comparator)
BinaryHeap
.isMinHeap
- true to use the order imposed by the given
comparator; false to reverse that ordercomparator
- the comparator used to order the elements, null
means use natural orderpublic 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.capacity
is <= 0
public BinaryHeap(int capacity, boolean isMinHeap, Comparator comparator)
BinaryHeap
.capacity
- the initial capacity for the heapisMinHeap
- true to use the order imposed by the given
comparator; false to reverse that ordercomparator
- the comparator used to order the elements, null
means use natural ordercapacity
is <= 0
Method Detail |
public void clear()
public boolean isEmpty()
true
if queue is empty; false
otherwise.public boolean isFull()
true
if queue is full; false
otherwise.public void insert(Object element)
element
- the element to be insertedpublic Object peek() throws NoSuchElementException
isEmpty() == true
public Object pop() throws NoSuchElementException
isEmpty() == true
protected void percolateDownMinHeap(int index)
index
- the index for the elementprotected void percolateDownMaxHeap(int index)
index
- the index of the elementprotected void percolateUpMinHeap(Object element)
element
- the elementprotected void percolateUpMaxHeap(Object element)
element
- the elementprotected void grow()
public String toString()
public Iterator iterator()
public boolean add(Object object)
insert(Object)
.object
- the object to addpublic Object get()
peek()
.public Object remove()
pop()
.public int size()
|
||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |