|
Keel 2.1RC2 | ||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||||
java.lang.Objectjava.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());
| Field Summary | |
private static int |
DEFAULT_CAPACITYThe default capacity for a binary heap. |
(package private) java.util.Comparator |
m_comparatorThe comparator used to order the elements |
(package private) java.lang.Object[] |
m_elementsThe elements in this heap. |
(package private) boolean |
m_isMinHeapIf true, the first element as determined by the sort order will be returned. |
(package private) int |
m_sizeThe number of elements currently in this heap. |
| 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. |
private int |
compare(java.lang.Object a, java.lang.Object b)Compares two objects using the comparator if specified, or the natural order otherwise. |
java.lang.Object |
get()Returns the priority element. |
protected void |
grow()Increases the size of the heap to support additional elements |
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. |
protected void |
percolateDownMaxHeap(int index)Percolates element down heap from top. |
protected void |
percolateDownMinHeap(int index)Percolates element down heap from top. |
protected void |
percolateUpMaxHeap(java.lang.Object element)Percolates element up heap from bottom. |
protected void |
percolateUpMinHeap(java.lang.Object element)Percolates element up heap from bottom. |
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 |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
| Methods inherited from interface java.util.Collection |
addAll, contains, containsAll, equals, hashCode, remove, removeAll, retainAll, toArray, toArray |
| Field Detail |
private static final int DEFAULT_CAPACITY
int m_size
java.lang.Object[] m_elements
boolean m_isMinHeap
java.util.Comparator m_comparator
| 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 orderjava.lang.IllegalArgumentException - if capacity is <= 0public BinaryHeap(boolean isMinHeap)
isMinHeap - if true the heap is created as a minimum heap; otherwise, the heap is created as a maximum heap
public 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 order
public 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 orderjava.lang.IllegalArgumentException - if capacity is <= 0| Method Detail |
public void clear()
clear in interface PriorityQueuepublic boolean isEmpty()
isEmpty in interface PriorityQueuetrue 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 PriorityQueueelement - the element to be inserted
public java.lang.Object peek()
throws java.util.NoSuchElementException
peek in interface PriorityQueuejava.util.NoSuchElementException - if isEmpty() == true
public java.lang.Object pop()
throws java.util.NoSuchElementException
pop in interface PriorityQueuejava.util.NoSuchElementException - if isEmpty() == trueprotected void percolateDownMinHeap(int index)
index - the index for the elementprotected void percolateDownMaxHeap(int index)
index - the index of the elementprotected void percolateUpMinHeap(java.lang.Object element)
element - the elementprotected void percolateUpMaxHeap(java.lang.Object element)
element - the element
private int compare(java.lang.Object a,
java.lang.Object b)
a - the first objectb - the second objectprotected void grow()
public java.lang.String toString()
public java.util.Iterator iterator()
iterator in interface java.util.Collectionpublic boolean add(java.lang.Object object)
insert(Object).
add in interface java.util.Collectionobject - the object to addpublic java.lang.Object get()
peek().
get in interface BufferBufferUnderflowException - if this heap is emptypublic java.lang.Object remove()
pop().
remove in interface BufferBufferUnderflowException - if this heap is emptypublic int size()
size in interface java.util.Collection
|
Keel 2.1RC2 | ||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||||