org.apache.commons.collections
public final class BinaryHeap extends AbstractCollection implements PriorityQueue, Buffer
Deprecated: Replaced by PriorityBuffer in buffer subpackage. Due to be removed in v4.0.
Binary heap implementation ofPriorityQueue
.
The PriorityQueue
interface has now been replaced for most uses
by the Buffer
interface. This class and the interface are
retained for backwards compatibility. The intended replacement is
PriorityBuffer
.
The removal order of a binary heap is based on either the natural sort
order of its elements or a specified Comparator. The
pop 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 pop
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 insert and pop operations perform in logarithmic time. The peek operation performs in constant time. All other operations perform in linear time or worse.
Note that this implementation is not synchronized. Use SynchronizedPriorityQueue
to provide synchronized access to a BinaryHeap
:
PriorityQueue heap = new SynchronizedPriorityQueue(new BinaryHeap());
Since: Commons Collections 1.0
Version: $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
Constructor Summary | |
---|---|
BinaryHeap()
Constructs a new minimum binary heap. | |
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, Comparator comparator)
Constructs a new BinaryHeap .
| |
BinaryHeap(boolean isMinHeap)
Constructs a new minimum or maximum binary heap
| |
BinaryHeap(boolean isMinHeap, Comparator comparator)
Constructs a new BinaryHeap .
| |
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 .
|
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 the position given by the index.
|
protected void | percolateDownMinHeap(int index)
Percolates element down heap from the position given by the index.
|
protected void | percolateUpMaxHeap(int index)
Percolates element up heap from from the position given by the index.
|
protected void | percolateUpMaxHeap(Object element)
Percolates a new element up heap from the bottom.
|
protected void | percolateUpMinHeap(int index)
Percolates element up heap from the position given by the index.
|
protected void | percolateUpMinHeap(Object element)
Percolates a new element up heap from the 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. |
BinaryHeap
that will use the given
comparator to order its elements.
Parameters: comparator the comparator used to order the elements, null means use natural order
Parameters: capacity The initial capacity for the heap. This value must be greater than zero.
Throws: IllegalArgumentException
if capacity
is <= 0
BinaryHeap
.
Parameters: capacity the initial capacity for the heap comparator the comparator used to order the elements, null means use natural order
Throws: IllegalArgumentException
if capacity
is <= 0
Parameters: isMinHeap if true
the heap is created as a
minimum heap; otherwise, the heap is created as a maximum heap
BinaryHeap
.
Parameters: isMinHeap true to use the order imposed by the given comparator; false to reverse that order comparator the comparator used to order the elements, null means use natural order
Parameters: 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.
Throws: IllegalArgumentException
if capacity
is <= 0
BinaryHeap
.
Parameters: capacity the initial capacity for the heap isMinHeap true to use the order imposed by the given comparator; false to reverse that order comparator the comparator used to order the elements, null means use natural order
Throws: IllegalArgumentException
if capacity
is <= 0
Parameters: object the object to add
Returns: true, always
Returns: the priority element
Throws: BufferUnderflowException if this heap is empty
Parameters: element the element to be inserted
Returns: true
if queue is empty; false
otherwise.
Returns: true
if queue is full; false
otherwise.
Returns: an iterator over this heap's elements
Returns: the element at top of heap
Throws: NoSuchElementException if isEmpty() == true
Assumes it is a maximum heap.
Parameters: index the index of the element
Assumes it is a minimum heap.
Parameters: index the index for the element
Assume it is a maximum heap.
Parameters: index the index of the element to be percolated up
Assume it is a maximum heap.
Parameters: element the element
Assumes it is a minimum heap.
Parameters: index the index of the element to be percolated up
Assumes it is a minimum heap.
Parameters: element the element
Returns: the element at top of heap
Throws: NoSuchElementException if isEmpty() == true
Returns: the removed priority element
Throws: BufferUnderflowException if this heap is empty
Returns: the number of elements in this heap
Returns: a string representation of this heap