org.apache.commons.collections
Class BinaryHeap

java.lang.Object
  |
  +--java.util.AbstractCollection
        |
        +--org.apache.commons.collections.BinaryHeap

public final class BinaryHeap
extends AbstractCollection
implements PriorityQueue, Buffer

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

Since:
1.0
Version:
$Id: BinaryHeap.java,v 1.11 2002/10/13 12:59:04 scolebourne Exp $
Author:
Peter Donald, Ram Chidambaram, Michael A. Smith, Paul Jack, Stephen Colebourne

Constructor Summary
BinaryHeap()
          Constructs a new minimum binary heap.
BinaryHeap(boolean isMinHeap)
          Constructs a new minimum or maximum binary heap
BinaryHeap(boolean isMinHeap, Comparator comparator)
          Constructs a new BinaryHeap.
BinaryHeap(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, Comparator comparator)
          Constructs a new BinaryHeap.
BinaryHeap(int capacity, Comparator comparator)
          Constructs a new BinaryHeap.
 
Method Summary
 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.
 
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
 

Constructor Detail

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.
Parameters:
comparator - 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.
Parameters:
capacity - The initial capacity for the heap. This value must be greater than zero.
Throws:
IllegalArgumentException - if capacity is <= 0

BinaryHeap

public BinaryHeap(int capacity,
                  Comparator comparator)
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:
IllegalArgumentException - if capacity is <= 0

BinaryHeap

public BinaryHeap(boolean isMinHeap)
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,
                  Comparator comparator)
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)
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:
IllegalArgumentException - if capacity is <= 0

BinaryHeap

public BinaryHeap(int capacity,
                  boolean isMinHeap,
                  Comparator comparator)
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:
IllegalArgumentException - if capacity is <= 0
Method Detail

clear

public void clear()
Clears all elements from queue.
Specified by:
clear in interface PriorityQueue
Overrides:
clear in class AbstractCollection

isEmpty

public boolean isEmpty()
Tests if queue is empty.
Specified by:
isEmpty in interface PriorityQueue
Overrides:
isEmpty in class AbstractCollection
Returns:
true if queue is empty; false otherwise.

isFull

public boolean isFull()
Tests if queue is full.
Returns:
true if queue is full; false otherwise.

insert

public void insert(Object element)
Inserts an element into queue.
Specified by:
insert in interface PriorityQueue
Parameters:
element - the element to be inserted

peek

public Object peek()
            throws NoSuchElementException
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:
NoSuchElementException - if isEmpty() == true

pop

public Object pop()
           throws NoSuchElementException
Returns the element on top of heap and remove it.
Specified by:
pop in interface PriorityQueue
Returns:
the element at top of heap
Throws:
NoSuchElementException - if isEmpty() == true

percolateDownMinHeap

protected void percolateDownMinHeap(int index)
Percolates element down heap from top. Assume it is a maximum heap.
Parameters:
index - the index for the element

percolateDownMaxHeap

protected void percolateDownMaxHeap(int index)
Percolates element down heap from top. Assume it is a maximum heap.
Parameters:
index - the index of the element

percolateUpMinHeap

protected void percolateUpMinHeap(Object element)
Percolates element up heap from bottom. Assume it is a maximum heap.
Parameters:
element - the element

percolateUpMaxHeap

protected void percolateUpMaxHeap(Object element)
Percolates element up heap from bottom. Assume it is a maximum heap.
Parameters:
element - the element

grow

protected void grow()
Increases the size of the heap to support additional elements

toString

public String toString()
Returns a string representation of this heap. The returned string is similar to those produced by standard JDK collections.
Overrides:
toString in class AbstractCollection
Returns:
a string representation of this heap

iterator

public Iterator iterator()
Returns an iterator over this heap's elements.
Overrides:
iterator in class AbstractCollection
Returns:
an iterator over this heap's elements

add

public boolean add(Object object)
Adds an object to this heap. Same as insert(Object).
Overrides:
add in class AbstractCollection
Parameters:
object - the object to add
Returns:
true, always

get

public Object get()
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 Object remove()
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()
Returns the number of elements in this heap.
Overrides:
size in class AbstractCollection
Returns:
the number of elements in this heap


Copyright © 2001-2002 Apache Software Foundation. Documenation generated October 21 2002.