public final class BinaryHeap extends java.util.AbstractCollection implements PriorityQueue, Buffer
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());
Constructor and Description |
---|
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 . |
Modifier and Type | Method and Description |
---|---|
boolean |
add(java.lang.Object object)
Adds an object to this heap.
|
void |
clear()
Clears all elements from queue.
|
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.
|
addAll, contains, containsAll, remove, removeAll, retainAll, toArray, toArray
public BinaryHeap()
public BinaryHeap(boolean isMinHeap)
isMinHeap
- if true
the heap is created as a
minimum heap; otherwise, the heap is created as a maximum heappublic 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 orderpublic 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, 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
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 <= 0
public boolean add(java.lang.Object object)
insert(Object)
.add
in interface java.util.Collection
add
in class java.util.AbstractCollection
object
- the object to addpublic void clear()
clear
in interface java.util.Collection
clear
in interface PriorityQueue
clear
in class java.util.AbstractCollection
public java.lang.Object get()
peek()
.get
in interface Buffer
BufferUnderflowException
- if this heap is emptyprotected void grow()
public void insert(java.lang.Object element)
insert
in interface PriorityQueue
element
- the element to be insertedpublic boolean isEmpty()
isEmpty
in interface java.util.Collection
isEmpty
in interface PriorityQueue
isEmpty
in class java.util.AbstractCollection
true
if queue is empty; false
otherwise.public boolean isFull()
true
if queue is full; false
otherwise.public java.util.Iterator iterator()
iterator
in interface java.lang.Iterable
iterator
in interface java.util.Collection
iterator
in class java.util.AbstractCollection
public java.lang.Object peek() throws java.util.NoSuchElementException
peek
in interface PriorityQueue
java.util.NoSuchElementException
- if isEmpty() == true
protected void percolateDownMaxHeap(int index)
index
- the index of the elementprotected void percolateDownMinHeap(int index)
index
- the index for the elementprotected void percolateUpMaxHeap(java.lang.Object element)
element
- the elementprotected void percolateUpMinHeap(java.lang.Object element)
element
- the elementpublic java.lang.Object pop() throws java.util.NoSuchElementException
pop
in interface PriorityQueue
java.util.NoSuchElementException
- if isEmpty() == true
public java.lang.Object remove()
pop()
.remove
in interface Buffer
BufferUnderflowException
- if this heap is emptypublic int size()
size
in interface java.util.Collection
size
in class java.util.AbstractCollection
public java.lang.String toString()
toString
in class java.util.AbstractCollection
Copyright © 2001-2004 Apache Software Foundation. Documenation generated April 29 2013.