AbstractCollection | +--org.apache.commons.collections.BinaryHeapAll Implemented Interfaces:
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. |
boolean | add(Object object) Adds an object to this heap. |
void | clear() Clears all elements from queue. |
Object | get() Returns the priority element. |
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. |
void | percolateDownMaxHeap(final int index) Percolates element down heap from the position given by the index. |
void | percolateDownMinHeap(final int index) Percolates element down heap from the position given by the index. |
void | percolateUpMaxHeap(final int index) Percolates element up heap from from the position given by the index. |
void | percolateUpMaxHeap(final Object element) Percolates a new element up heap from the bottom. |
void | percolateUpMinHeap(final int index) Percolates element up heap from the position given by the index. |
void | percolateUpMinHeap(final 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. |
public BinaryHeap()
public BinaryHeap(boolean isMinHeap, Comparator comparator)
BinaryHeap
.
public BinaryHeap(boolean isMinHeap)
public BinaryHeap(Comparator comparator)
BinaryHeap
that will use the given
comparator to order its elements.
public BinaryHeap(int capacity, boolean isMinHeap, Comparator comparator)
BinaryHeap
.
- if capacity is <= 0public BinaryHeap(int capacity, boolean isMinHeap)
- if capacity is <= 0public BinaryHeap(int capacity, Comparator comparator)
BinaryHeap
.
- if capacity is <= 0public BinaryHeap(int capacity)
- if capacity is <= 0public boolean add(Object object)
public void clear()
public Object get()
BufferUnderflowException
- if this heap is emptyprotected void grow()
public void insert(Object element)
public boolean isEmpty()
public boolean isFull()
public Iterator iterator()
public Object peek()
- if isEmpty() == trueprotected void percolateDownMaxHeap(final int index)
protected void percolateDownMinHeap(final int index)
protected void percolateUpMaxHeap(final int index)
protected void percolateUpMaxHeap(final Object element)
protected void percolateUpMinHeap(final int index)
protected void percolateUpMinHeap(final Object element)
public Object pop()
- if isEmpty() == truepublic Object remove()
BufferUnderflowException
- if this heap is emptypublic int size()
public String toString()
PriorityQueue
. ThePriorityQueue
interface has now been replaced for most uses by theBuffer
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 pop() method always returns the first element as determined by the sort order. (TheisMinHeap
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(Object) 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 aBinaryHeap
: