org.apache.commons.collections
Class BinaryHeap

java.lang.Object
  java.util.AbstractCollection
      org.apache.commons.collections.BinaryHeap

All Implemented Interfaces:

java.lang.Iterable, java.util.Collection, Buffer, PriorityQueue

Deprecated. Replaced by PriorityBuffer in buffer subpackage. Due to be removed in v4.0.

public final class BinaryHeap
extends java.util.AbstractCollection
implements PriorityQueue, Buffer

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());
 

Since:

Commons Collections 1.0

Version:

$Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $

Author:

Peter Donald, Ram Chidambaram, Michael A. Smith, Paul Jack, Stephen Colebourne

Constructor Summary

BinaryHeap()
Deprecated. Constructs a new minimum binary heap.

BinaryHeap(boolean isMinHeap)
Deprecated. Constructs a new minimum or maximum binary heap

BinaryHeap(boolean isMinHeap, java.util.Comparator comparator)
Deprecated. Constructs a new BinaryHeap.

BinaryHeap(java.util.Comparator comparator)
Deprecated. Constructs a new BinaryHeap that will use the given comparator to order its elements.

BinaryHeap(int capacity)
Deprecated. Constructs a new minimum binary heap with the specified initial capacity.

BinaryHeap(int capacity, boolean isMinHeap)
Deprecated. Constructs a new minimum or maximum binary heap with the specified initial capacity.

BinaryHeap(int capacity, boolean isMinHeap, java.util.Comparator comparator)
Deprecated. Constructs a new BinaryHeap.

BinaryHeap(int capacity, java.util.Comparator comparator)
Deprecated. Constructs a new BinaryHeap.

Method Summary

boolean	add(java.lang.Object object) Deprecated. Adds an object to this heap.
void	clear() Deprecated. Clears all elements from queue.
java.lang.Object	get() Deprecated. Returns the priority element.
protected void	grow() Deprecated. Increases the size of the heap to support additional elements
void	insert(java.lang.Object element) Deprecated. Inserts an element into queue.
boolean	isEmpty() Deprecated. Tests if queue is empty.
boolean	isFull() Deprecated. Tests if queue is full.
java.util.Iterator	iterator() Deprecated. Returns an iterator over this heap's elements.
java.lang.Object	peek() Deprecated. Returns the element on top of heap but don't remove it.
protected void	percolateDownMaxHeap(int index) Deprecated. Percolates element down heap from the position given by the index.
protected void	percolateDownMinHeap(int index) Deprecated. Percolates element down heap from the position given by the index.
protected void	percolateUpMaxHeap(int index) Deprecated. Percolates element up heap from from the position given by the index.
protected void	percolateUpMaxHeap(java.lang.Object element) Deprecated. Percolates a new element up heap from the bottom.
protected void	percolateUpMinHeap(int index) Deprecated. Percolates element up heap from the position given by the index.
protected void	percolateUpMinHeap(java.lang.Object element) Deprecated. Percolates a new element up heap from the bottom.
java.lang.Object	pop() Deprecated. Returns the element on top of heap and remove it.
java.lang.Object	remove() Deprecated. Removes the priority element.
int	size() Deprecated. Returns the number of elements in this heap.
java.lang.String	toString() Deprecated. 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

Constructor Detail

BinaryHeap

public BinaryHeap()

Deprecated.

Constructs a new minimum binary heap.

BinaryHeap

public BinaryHeap(java.util.Comparator comparator)

Deprecated.

Constructs a new BinaryHeap that will use the given comparator to order its elements.

Parameters:

comparator - the comparator used to order the elements, null means use natural order

BinaryHeap

public BinaryHeap(int capacity)

Deprecated.

Constructs a new minimum binary heap with the specified initial capacity.

Parameters:

capacity - The initial capacity for the heap. This value must be greater than zero.

Throws:

java.lang.IllegalArgumentException - if capacity is <= 0

BinaryHeap

public BinaryHeap(int capacity,
                  java.util.Comparator comparator)

Deprecated.

Constructs a new BinaryHeap.

Parameters:

capacity - the initial capacity for the heap

comparator - the comparator used to order the elements, null means use natural order

Throws:

java.lang.IllegalArgumentException - if capacity is <= 0

BinaryHeap

public BinaryHeap(boolean isMinHeap)

Deprecated.

Constructs a new minimum or maximum binary heap

Parameters:

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,
                  java.util.Comparator comparator)

Deprecated.

Constructs a new BinaryHeap.

Parameters:

isMinHeap - true to use the order imposed by the given comparator; false to reverse that order

comparator - the comparator used to order the elements, null means use natural order

BinaryHeap

public BinaryHeap(int capacity,
                  boolean isMinHeap)

Deprecated.

Constructs a new minimum or maximum binary heap with the specified initial capacity.

Parameters:

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.

Throws:

java.lang.IllegalArgumentException - if capacity is <= 0

BinaryHeap

public BinaryHeap(int capacity,
                  boolean isMinHeap,
                  java.util.Comparator comparator)

Deprecated.

Constructs a new BinaryHeap.

Parameters:

capacity - the initial capacity for the heap

isMinHeap - true to use the order imposed by the given comparator; false to reverse that order

comparator - the comparator used to order the elements, null means use natural order

Throws:

java.lang.IllegalArgumentException - if capacity is <= 0

Method Detail

clear

public void clear()

Deprecated.

Clears all elements from queue.

Specified by:

clear in interface java.util.Collection

Specified by:

clear in interface PriorityQueue

Overrides:

clear in class java.util.AbstractCollection

isEmpty

public boolean isEmpty()

Deprecated.

Tests if queue is empty.

Specified by:

isEmpty in interface java.util.Collection

Specified by:

isEmpty in interface PriorityQueue

Overrides:

isEmpty in class java.util.AbstractCollection

Returns:

true if queue is empty; false otherwise.

isFull

public boolean isFull()

Deprecated.

Tests if queue is full.

Returns:

true if queue is full; false otherwise.

insert

public void insert(java.lang.Object element)

Deprecated.

Inserts an element into queue.

Specified by:

insert in interface PriorityQueue

Parameters:

element - the element to be inserted

peek

public java.lang.Object peek()
                      throws java.util.NoSuchElementException

Deprecated.

Returns the element on top of heap but don't remove it.

Specified by:

peek in interface PriorityQueue

Returns:

the element at top of heap

Throws:

java.util.NoSuchElementException - if isEmpty() == true

pop

public java.lang.Object pop()
                     throws java.util.NoSuchElementException

Deprecated.

Returns the element on top of heap and remove it.

Specified by:

pop in interface PriorityQueue

Returns:

the element at top of heap

Throws:

java.util.NoSuchElementException - if isEmpty() == true

percolateDownMinHeap

protected void percolateDownMinHeap(int index)

Deprecated.

Percolates element down heap from the position given by the index.

Assumes it is a minimum heap.

Parameters:

index - the index for the element

percolateDownMaxHeap

protected void percolateDownMaxHeap(int index)

Deprecated.

Percolates element down heap from the position given by the index.

Assumes it is a maximum heap.

Parameters:

index - the index of the element

percolateUpMinHeap

protected void percolateUpMinHeap(int index)

Deprecated.

Percolates element up heap from the position given by the index.

Assumes it is a minimum heap.

Parameters:

index - the index of the element to be percolated up

percolateUpMinHeap

protected void percolateUpMinHeap(java.lang.Object element)

Deprecated.

Percolates a new element up heap from the bottom.

Assumes it is a minimum heap.

Parameters:

element - the element

percolateUpMaxHeap

protected void percolateUpMaxHeap(int index)

Deprecated.

Percolates element up heap from from the position given by the index.

Assume it is a maximum heap.

Parameters:

index - the index of the element to be percolated up

percolateUpMaxHeap

protected void percolateUpMaxHeap(java.lang.Object element)

Deprecated.

Percolates a new element up heap from the bottom.

Assume it is a maximum heap.

Parameters:

element - the element

grow

protected void grow()

Deprecated.

Increases the size of the heap to support additional elements

toString

public java.lang.String toString()

Deprecated.

Returns a string representation of this heap. The returned string is similar to those produced by standard JDK collections.

Overrides:

toString in class java.util.AbstractCollection

Returns:

a string representation of this heap

iterator

public java.util.Iterator iterator()

Deprecated.

Returns an iterator over this heap's elements.

Specified by:

iterator in interface java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in class java.util.AbstractCollection

Returns:

an iterator over this heap's elements

add

public boolean add(java.lang.Object object)

Deprecated.

Adds an object to this heap. Same as insert(Object).

Specified by:

add in interface java.util.Collection

Overrides:

add in class java.util.AbstractCollection

Parameters:

object - the object to add

Returns:

true, always

get

public java.lang.Object get()

Deprecated.

Returns the priority element. Same as peek().

Specified by:

get in interface Buffer

Returns:

the priority element

Throws:

BufferUnderflowException - if this heap is empty

remove

public java.lang.Object remove()

Deprecated.

Removes the priority element. Same as pop().

Specified by:

remove in interface Buffer

Returns:

the removed priority element

Throws:

BufferUnderflowException - if this heap is empty

size

public int size()

Deprecated.

Returns the number of elements in this heap.

Specified by:

size in interface java.util.Collection

Specified by:

size in class java.util.AbstractCollection

Returns:

the number of elements in this heap