public final class

BinaryHeap

extends AbstractCollection<E>
implements Buffer PriorityQueue
java.lang.Object
   ↳ java.util.AbstractCollection<E>
     ↳ org.apache.commons.collections.BinaryHeap

This class is deprecated.
Replaced by PriorityBuffer in buffer subpackage. Due to be removed in v4.0.

Class Overview

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

Summary

Public Constructors
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.
Public Methods
boolean add(Object object)
Adds an object to this heap.
void clear()
Clears all elements from queue.
Object get()
Returns the priority element.
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.
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.
Protected Methods
void grow()
Increases the size of the heap to support additional elements
void percolateDownMaxHeap(int index)
Percolates element down heap from the position given by the index.
void percolateDownMinHeap(int index)
Percolates element down heap from the position given by the index.
void percolateUpMaxHeap(Object element)
Percolates a new element up heap from the bottom.
void percolateUpMaxHeap(int index)
Percolates element up heap from from the position given by the index.
void percolateUpMinHeap(Object element)
Percolates a new element up heap from the bottom.
void percolateUpMinHeap(int index)
Percolates element up heap from the position given by the index.
[Expand]
Inherited Methods
From class java.util.AbstractCollection
From class java.lang.Object
From interface java.lang.Iterable
From interface java.util.Collection
From interface org.apache.commons.collections.Buffer
From interface org.apache.commons.collections.PriorityQueue

Public Constructors

public BinaryHeap ()

Constructs a new minimum binary heap.

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

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

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

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

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

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

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

Public Methods

public boolean add (Object object)

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

Parameters
object the object to add
Returns
  • true, always

public void clear ()

Clears all elements from queue.

public Object get ()

Returns the priority element. Same as peek().

Returns
  • the priority element
Throws
BufferUnderflowException if this heap is empty

public void insert (Object element)

Inserts an element into queue.

Parameters
element the element to be inserted

public boolean isEmpty ()

Tests if queue is empty.

Returns
  • true if queue is empty; false otherwise.

public boolean isFull ()

Tests if queue is full.

Returns
  • true if queue is full; false otherwise.

public Iterator iterator ()

Returns an iterator over this heap's elements.

Returns
  • an iterator over this heap's elements

public Object peek ()

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

Returns
  • the element at top of heap
Throws
NoSuchElementException if isEmpty() == true

public Object pop ()

Returns the element on top of heap and remove it.

Returns
  • the element at top of heap
Throws
NoSuchElementException if isEmpty() == true

public Object remove ()

Removes the priority element. Same as pop().

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

public int size ()

Returns the number of elements in this heap.

Returns
  • the number of elements in this heap

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

Protected Methods

protected void grow ()

Increases the size of the heap to support additional elements

protected void percolateDownMaxHeap (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

protected void percolateDownMinHeap (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

protected void percolateUpMaxHeap (Object element)

Percolates a new element up heap from the bottom.

Assume it is a maximum heap.

Parameters
element the element

protected void percolateUpMaxHeap (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

protected void percolateUpMinHeap (Object element)

Percolates a new element up heap from the bottom.

Assumes it is a minimum heap.

Parameters
element the element

protected void percolateUpMinHeap (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