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
.
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
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. (The
isMinHeap
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 a
BinaryHeap
:
PriorityQueue heap = new SynchronizedPriorityQueue(new BinaryHeap());
$Revision: 1.24 $ $Date: 2004/02/18 01:15:42 $- Peter Donald
- Ram Chidambaram
- Michael A. Smith
- Paul Jack
- Stephen Colebourne
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 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(Object element) - Percolates a new element up heap from the bottom.
|
protected void | percolateUpMaxHeap(int index) - Percolates element up heap from from the position given by the index.
|
protected void | percolateUpMinHeap(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.
|
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 the position given by the index.
Assumes it is a maximum heap.
index
- the index of the element
percolateDownMinHeap
protected void percolateDownMinHeap(int index)
Percolates element down heap from the position given by the index.
Assumes it is a minimum heap.
index
- the index for the element
percolateUpMaxHeap
protected void percolateUpMaxHeap(Object element)
Percolates a new element up heap from the bottom.
Assume it is a maximum heap.
percolateUpMaxHeap
protected void percolateUpMaxHeap(int index)
Percolates element up heap from from the position given by the index.
Assume it is a maximum heap.
index
- the index of the element to be percolated up
percolateUpMinHeap
protected void percolateUpMinHeap(Object element)
Percolates a new element up heap from the bottom.
Assumes it is a minimum heap.
percolateUpMinHeap
protected void percolateUpMinHeap(int index)
Percolates element up heap from the position given by the index.
Assumes it is a minimum heap.
index
- the index of the element to be percolated up
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-2006 Apache Software Foundation. All Rights Reserved.