org.apache.commons.collections
Class BinaryHeap
AbstractCollection
org.apache.commons.collections.BinaryHeap
- Buffer, Collection, PriorityQueue
public final class BinaryHeap
extends AbstractCollection
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());
$Id: BinaryHeap.java,v 1.11.2.1 2004/05/22 12:14:02 scolebourne Exp $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(boolean isMinHeap) - Constructs a new minimum or maximum binary heap
|
BinaryHeap(boolean isMinHeap, Comparator comparator) - Constructs a new
BinaryHeap .
|
BinaryHeap(int capacity) - Constructs a new minimum binary heap with the specified initial capacity.
|
BinaryHeap(int capacity, 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.
|
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 top.
|
protected void | percolateDownMinHeap(int index) - Percolates element down heap from top.
|
protected void | percolateUpMaxHeap(Object element) - Percolates element up heap from bottom.
|
protected void | percolateUpMinHeap(Object element) - Percolates element up heap from 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
public BinaryHeap()
Constructs a new minimum binary heap.
BinaryHeap
public BinaryHeap(Comparator comparator)
Constructs a new BinaryHeap
that will use the given
comparator to order its elements.
comparator
- the comparator used to order the elements, null
means use natural order
BinaryHeap
public BinaryHeap(boolean isMinHeap)
Constructs a new minimum or maximum binary heap
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)
Constructs a new 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
BinaryHeap
public BinaryHeap(int capacity)
Constructs a new minimum binary heap with the specified initial capacity.
capacity
- The initial capacity for the heap. This value must
be greater than zero.
BinaryHeap
public BinaryHeap(int capacity,
Comparator comparator)
Constructs a new BinaryHeap
.
capacity
- the initial capacity for the heapcomparator
- the comparator used to order the elements, null
means use natural order
BinaryHeap
public BinaryHeap(int capacity,
boolean isMinHeap)
Constructs a new minimum or maximum binary heap with the specified
initial capacity.
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.
BinaryHeap
public BinaryHeap(int capacity,
boolean isMinHeap,
Comparator comparator)
Constructs a new 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 order
add
public boolean add(Object object)
object
- the object to add
get
public Object get()
Returns the priority element. Same as
peek()
.
- get in interface Buffer
grow
protected void grow()
Increases the size of the heap to support additional elements
insert
public void insert(Object element)
Inserts an element into queue.
- insert in interface PriorityQueue
element
- the element to be inserted
isEmpty
public boolean isEmpty()
Tests if queue is empty.
- isEmpty in interface PriorityQueue
true
if queue is empty; false
otherwise.
isFull
public boolean isFull()
Tests if queue is full.
true
if queue is full; false
otherwise.
iterator
public Iterator iterator()
Returns an iterator over this heap's elements.
- an iterator over this heap's elements
peek
public Object peek()
throws NoSuchElementException
Returns the element on top of heap but don't remove it.
- peek in interface PriorityQueue
- the element at top of heap
percolateDownMaxHeap
protected void percolateDownMaxHeap(int index)
Percolates element down heap from top.
Assume it is a maximum heap.
index
- the index of the element
percolateDownMinHeap
protected void percolateDownMinHeap(int index)
Percolates element down heap from top.
Assume it is a maximum heap.
index
- the index for the element
percolateUpMaxHeap
protected void percolateUpMaxHeap(Object element)
Percolates element up heap from bottom.
Assume it is a maximum heap.
percolateUpMinHeap
protected void percolateUpMinHeap(Object element)
Percolates element up heap from bottom.
Assume it is a maximum heap.
pop
public Object pop()
throws NoSuchElementException
Returns the element on top of heap and remove it.
- pop in interface PriorityQueue
- the element at top of heap
remove
public Object remove()
Removes the priority element. Same as
pop()
.
- remove in interface Buffer
- the removed priority element
size
public int size()
Returns the number of elements in this heap.
- the number of elements in this heap
toString
public String toString()
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
Copyright © 2001-2004 Apache Software Foundation. Documenation generated ${TODAY}.