|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | 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,
java.util.Comparator comparator)
Constructs a new BinaryHeap . |
|
BinaryHeap(java.util.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,
java.util.Comparator comparator)
Constructs a new BinaryHeap . |
|
BinaryHeap(int capacity,
java.util.Comparator comparator)
Constructs a new BinaryHeap . |
Method Summary | |
boolean |
add(java.lang.Object object)
Adds an object to this heap. |
void |
clear()
Clears all elements from queue. |
java.lang.Object |
get()
Returns the priority element. |
void |
insert(java.lang.Object element)
Inserts an element into queue. |
boolean |
isEmpty()
Tests if queue is empty. |
boolean |
isFull()
Tests if queue is full. |
java.util.Iterator |
iterator()
Returns an iterator over this heap's elements. |
java.lang.Object |
peek()
Returns the element on top of heap but don't remove it. |
java.lang.Object |
pop()
Returns the element on top of heap and remove it. |
java.lang.Object |
remove()
Removes the priority element. |
int |
size()
Returns the number of elements in this heap. |
java.lang.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 |
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Methods inherited from interface java.util.Collection |
addAll, contains, containsAll, equals, hashCode, remove, removeAll, retainAll, toArray, toArray |
Constructor Detail |
public BinaryHeap()
public BinaryHeap(java.util.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.
java.lang.IllegalArgumentException
- if capacity
is <= 0
public BinaryHeap(int capacity, java.util.Comparator comparator)
BinaryHeap
.
capacity
- the initial capacity for the heapcomparator
- the comparator used to order the elements, null
means use natural order
java.lang.IllegalArgumentException
- if capacity
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, java.util.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.
java.lang.IllegalArgumentException
- if capacity
is <= 0
public BinaryHeap(int capacity, boolean isMinHeap, java.util.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 order
java.lang.IllegalArgumentException
- if capacity
is <= 0
Method Detail |
public void clear()
clear
in interface PriorityQueue
clear
in class java.util.AbstractCollection
public boolean isEmpty()
isEmpty
in interface PriorityQueue
isEmpty
in class java.util.AbstractCollection
true
if queue is empty; false
otherwise.public boolean isFull()
true
if queue is full; false
otherwise.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() == true
public java.lang.Object pop() throws java.util.NoSuchElementException
pop
in interface PriorityQueue
java.util.NoSuchElementException
- if isEmpty() == true
public java.lang.String toString()
toString
in class java.util.AbstractCollection
public java.util.Iterator iterator()
iterator
in interface java.util.Collection
iterator
in class java.util.AbstractCollection
public boolean add(java.lang.Object object)
insert(Object)
.
add
in interface java.util.Collection
add
in class java.util.AbstractCollection
object
- the object to add
public java.lang.Object get()
peek()
.
get
in interface Buffer
BufferUnderflowException
- if this heap is emptypublic java.lang.Object remove()
pop()
.
remove
in interface Buffer
BufferUnderflowException
- if this heap is emptypublic int size()
size
in interface java.util.Collection
size
in class java.util.AbstractCollection
|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |