|
| |
|
| java.lang.Object
 java.util.AbstractCollection
org.apache.commons.collections.BinaryHeap
| BinaryHeap | | final public class BinaryHeap extends AbstractCollection implements PriorityQueue,Buffer(Code) | | Binary heap implementation of PriorityQueue.
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
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
Comparator . The
BinaryHeap.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
BinaryHeap.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
BinaryHeap.insert(Object) and
BinaryHeap.pop() operations perform
in logarithmic time. The
BinaryHeap.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) $
author:
Peter Donald
author:
Ram Chidambaram
author:
Michael A. Smith
author:
Paul Jack
author:
Stephen Colebourne |
| Constructor Summary | |
| public | BinaryHeap()
Constructs a new minimum binary heap. | | public | BinaryHeap(Comparator comparator)
Constructs a new BinaryHeap that will use the given
comparator to order its elements. | | public | BinaryHeap(int capacity)
Constructs a new minimum binary heap with the specified initial capacity.
Parameters:
capacity - The initial capacity for the heap. | | public | BinaryHeap(int capacity, Comparator comparator)
Constructs a new BinaryHeap. | | public | BinaryHeap(boolean isMinHeap)
| | public | BinaryHeap(boolean isMinHeap, Comparator comparator)
Constructs a new BinaryHeap. | | public | BinaryHeap(int capacity, boolean isMinHeap)
Constructs a new minimum or maximum binary heap with the specified
initial capacity.
Parameters:
capacity - the initial capacity for the heap. | | public | BinaryHeap(int capacity, boolean isMinHeap, Comparator comparator)
Constructs a new BinaryHeap. |
| Method Summary | |
| public boolean | add(Object object)
Adds an object to this heap. | | public void | clear()
Clears all elements from queue. | | public Object | get()
Returns the priority element. | | protected void | grow()
| | public void | insert(Object element)
Inserts an element into queue. | | public boolean | isEmpty()
Tests if queue is empty. | | public boolean | isFull()
Tests if queue is full. | | public Iterator | iterator()
Returns an iterator over this heap's elements. | | public 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. | | public Object | pop()
Returns the element on top of heap and remove it. | | public Object | remove()
Removes the priority element. | | public int | size()
Returns the number of elements in this heap. | | public String | toString()
Returns a string representation of this heap. |
| m_comparator | | Comparator m_comparator(Code) | | The comparator used to order the elements
|
| m_elements | | Object[] m_elements(Code) | | The elements in this heap.
|
| m_isMinHeap | | boolean m_isMinHeap(Code) | | If true, the first element as determined by the sort order will
be returned. If false, the last element as determined by the
sort order will be returned.
|
| m_size | | int m_size(Code) | | The number of elements currently in this heap.
|
| BinaryHeap | | public BinaryHeap()(Code) | | Constructs a new minimum binary heap.
|
| BinaryHeap | | public BinaryHeap(Comparator comparator)(Code) | | Constructs a new BinaryHeap that will use the given
comparator to order its elements.
Parameters:
comparator - the comparator used to order the elements, nullmeans use natural order |
| BinaryHeap | | public BinaryHeap(int capacity)(Code) | | Constructs a new minimum binary heap with the specified initial capacity.
Parameters:
capacity - The initial capacity for the heap. This value mustbe greater than zero.
throws:
IllegalArgumentException - if capacity is <= 0 |
| BinaryHeap | | public BinaryHeap(int capacity, Comparator comparator)(Code) | | Constructs a new BinaryHeap.
Parameters:
capacity - the initial capacity for the heap
Parameters:
comparator - the comparator used to order the elements, nullmeans use natural order
throws:
IllegalArgumentException - if capacity is <= 0 |
| BinaryHeap | | public BinaryHeap(boolean isMinHeap)(Code) | | Constructs a new minimum or maximum binary heap
Parameters:
isMinHeap - if true the heap is created as a minimum heap; otherwise, the heap is created as a maximum heap |
| BinaryHeap | | public BinaryHeap(boolean isMinHeap, Comparator comparator)(Code) | | Constructs a new BinaryHeap.
Parameters:
isMinHeap - true to use the order imposed by the given comparator; false to reverse that order
Parameters:
comparator - the comparator used to order the elements, nullmeans use natural order |
| BinaryHeap | | public BinaryHeap(int capacity, boolean isMinHeap)(Code) | | Constructs a new minimum or maximum binary heap with the specified
initial capacity.
Parameters:
capacity - the initial capacity for the heap. This value must be greater than zero.
Parameters:
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 | | public BinaryHeap(int capacity, boolean isMinHeap, Comparator comparator)(Code) | | Constructs a new BinaryHeap.
Parameters:
capacity - the initial capacity for the heap
Parameters:
isMinHeap - true to use the order imposed by the given comparator; false to reverse that order
Parameters:
comparator - the comparator used to order the elements, nullmeans use natural order
throws:
IllegalArgumentException - if capacity is <= 0 |
| clear | | public void clear()(Code) | | Clears all elements from queue.
|
| grow | | protected void grow()(Code) | | Increases the size of the heap to support additional elements
|
| insert | | public void insert(Object element)(Code) | | Inserts an element into queue.
Parameters:
element - the element to be inserted |
| isEmpty | | public boolean isEmpty()(Code) | | Tests if queue is empty.
true if queue is empty; false otherwise. |
| isFull | | public boolean isFull()(Code) | | Tests if queue is full.
true if queue is full; falseotherwise. |
| iterator | | public Iterator iterator()(Code) | | Returns an iterator over this heap's elements.
an iterator over this heap's elements |
| percolateDownMaxHeap | | protected void percolateDownMaxHeap(int index)(Code) | | Percolates element down heap from the position given by the index.
Assumes it is a maximum heap.
Parameters:
index - the index of the element |
| percolateDownMinHeap | | protected void percolateDownMinHeap(int index)(Code) | | Percolates element down heap from the position given by the index.
Assumes it is a minimum heap.
Parameters:
index - the index for the element |
| percolateUpMaxHeap | | protected void percolateUpMaxHeap(int index)(Code) | | Percolates element up heap from from the position given by the index.
Assume it is a maximum heap.
Parameters:
index - the index of the element to be percolated up |
| percolateUpMaxHeap | | protected void percolateUpMaxHeap(Object element)(Code) | | Percolates a new element up heap from the bottom.
Assume it is a maximum heap.
Parameters:
element - the element |
| percolateUpMinHeap | | protected void percolateUpMinHeap(int index)(Code) | | Percolates element up heap from the position given by the index.
Assumes it is a minimum heap.
Parameters:
index - the index of the element to be percolated up |
| percolateUpMinHeap | | protected void percolateUpMinHeap(Object element)(Code) | | Percolates a new element up heap from the bottom.
Assumes it is a minimum heap.
Parameters:
element - the element |
| size | | public int size()(Code) | | Returns the number of elements in this heap.
the number of elements in this heap |
| toString | | public String toString()(Code) | | Returns a string representation of this heap. The returned string
is similar to those produced by standard JDK collections.
a string representation of this heap |
|
|
|