⇒ Index (Frames) |  ⇒ Index (No Frames) |  ⇒ Package |  ⇒ Package Tree |  ⇒ Full Tree 
org.apache.commons.collections

Class BinaryHeap

AbstractCollection
|
+--org.apache.commons.collections.BinaryHeap

All Implemented Interfaces:
Buffer, PriorityQueue


public final class BinaryHeap
extends 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 org.apache.commons.collections.buffer.PriorityBuffer 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
Authors:
Peter Donald
Ram Chidambaram
Michael A. Smith
Paul Jack
Stephen Colebourne

Constructor Summary

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(int capacity)

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

BinaryHeap(int capacity, Comparator comparator)

Constructs a new BinaryHeap.

BinaryHeap(boolean isMinHeap)

Constructs a new minimum or maximum binary heap

BinaryHeap(boolean isMinHeap, 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.

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.

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.

void

percolateDownMaxHeap(final int index)

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

void

percolateDownMinHeap(final int index)

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

void

percolateUpMaxHeap(final int index)

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

void

percolateUpMaxHeap(final Object element)

Percolates a new element up heap from the bottom.

void

percolateUpMinHeap(final int index)

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

void

percolateUpMinHeap(final Object element)

Percolates a new element up heap from the 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.

Constructor Details

BinaryHeap

public BinaryHeap()

Constructs a new minimum binary 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(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(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, 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:
- if capacity is <= 0

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.
isMinHeap - if true the heap is created as a minimum heap; otherwise, the heap is created as a maximum heap.
Throws:
- 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:
- if capacity is <= 0

BinaryHeap

public BinaryHeap(int capacity)

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

Parameters:
capacity - The initial capacity for the heap.
Throws:
- if capacity is <= 0

Method Details

add

public boolean add(Object object)

Parameters:
object - the object to add
Returns:
true, always

clear

public void clear()

Clears all elements from queue.


get

public Object get()

Returns:
the priority element
Throws:
BufferUnderflowException - if this heap is empty

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.

Parameters:
element - the element to be inserted

isEmpty

public boolean isEmpty()

Tests if queue is empty.

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.

iterator

public Iterator iterator()

Returns an iterator over this heap's elements.

Returns:
an iterator over this heap's elements

peek

public Object peek()

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

Returns:
the element at top of heap
Throws:
- if isEmpty() == true

percolateDownMaxHeap

protected void percolateDownMaxHeap(final int index)

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

Assumes it is a maximum heap.

Parameters:
index - the index of the element

percolateDownMinHeap

protected void percolateDownMinHeap(final int index)

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

Assumes it is a minimum heap.

Parameters:
index - the index for the element

percolateUpMaxHeap

protected void percolateUpMaxHeap(final int index)

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(final Object element)

Percolates a new element up heap from the bottom.

Assume it is a maximum heap.

Parameters:
element - the element

percolateUpMinHeap

protected void percolateUpMinHeap(final int index)

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(final Object element)

Percolates a new element up heap from the bottom.

Assumes it is a minimum heap.

Parameters:
element - the element

pop

public Object pop()

Returns the element on top of heap and remove it.

Returns:
the element at top of heap
Throws:
- if isEmpty() == true

remove

public Object remove()

Returns:
the removed priority element
Throws:
BufferUnderflowException - if this heap is empty

size

public int size()

Returns the number of elements in this heap.

Returns:
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.

Returns:
a string representation of this heap