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
{@link org.apache.commons.collections.buffer.PriorityBuffer PriorityBuffer}.
The removal order of a binary heap is based on either the natural sort
order of its elements or a specified {@link Comparator}. The
{@link #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 {@link #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 {@link #insert(Object)} and {@link #pop()} operations perform in logarithmic time. The {@link #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: 1.24 $ $Date: 2004/02/18 01:15:42 $
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