BinaryHeap (Apache Commons Collections 3.2.2 API)

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

All Implemented Interfaces:

Iterable, Collection, Buffer, PriorityQueue

Deprecated.
Replaced by PriorityBuffer in buffer subpackage. Due to be removed in v4.0.
```
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 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: 972404 $ $Date: 2008-04-10 14:33:15 +0200 (Thu, 10 Apr 2008) $

Author:

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

Constructor Summary

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

Method Summary

Methods
Modifier and Type	Method and Description
`boolean`	`add(Object object)` Deprecated. Adds an object to this heap.
`void`	`clear()` Deprecated. Clears all elements from queue.
`Object`	`get()` Deprecated. Returns the priority element.
`protected void`	`grow()` Deprecated. Increases the size of the heap to support additional elements
`void`	`insert(Object element)` Deprecated. Inserts an element into queue.
`boolean`	`isEmpty()` Deprecated. Tests if queue is empty.
`boolean`	`isFull()` Deprecated. Tests if queue is full.
`Iterator`	`iterator()` Deprecated. Returns an iterator over this heap's elements.
`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(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(Object element)` Deprecated. Percolates a new element up heap from the bottom.
`Object`	`pop()` Deprecated. Returns the element on top of heap and remove it.
`Object`	`remove()` Deprecated. Removes the priority element.
`int`	`size()` Deprecated. Returns the number of elements in this heap.
`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(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:
    
    IllegalArgumentException - if capacity is <= 0
  - BinaryHeap
```
public BinaryHeap(int capacity,
          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:
    
    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,
          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:
    
    IllegalArgumentException - if capacity is <= 0
  - BinaryHeap
```
public BinaryHeap(int capacity,
          boolean isMinHeap,
          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:
    
    IllegalArgumentException - if capacity is <= 0
- Method Detail
  - clear
```
public void clear()
```
    Deprecated.
    
    Clears all elements from queue.
    
    Specified by:
    
    clear in interface Collection
    
    Specified by:
    
    clear in interface PriorityQueue
    
    Overrides:
    
    clear in class AbstractCollection
  - isEmpty
```
public boolean isEmpty()
```
    Deprecated.
    
    Tests if queue is empty.
    
    Specified by:
    
    isEmpty in interface Collection
    
    Specified by:
    
    isEmpty in interface PriorityQueue
    
    Overrides:
    
    isEmpty in class 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(Object element)
```
    Deprecated.
    
    Inserts an element into queue.
    
    Specified by:
    
    insert in interface PriorityQueue
    
    Parameters:
    element - the element to be inserted
  - peek
```
public Object peek()
            throws 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:
    
    NoSuchElementException - if isEmpty() == true
  - pop
```
public Object pop()
           throws 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:
    
    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(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(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 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 AbstractCollection
    
    Returns:
    a string representation of this heap
  - iterator
```
public Iterator iterator()
```
    Deprecated.
    
    Returns an iterator over this heap's elements.
    
    Specified by:
    
    iterator in interface Iterable
    
    Specified by:
    
    iterator in interface Collection
    
    Specified by:
    
    iterator in class AbstractCollection
    
    Returns:
    an iterator over this heap's elements
  - add
```
public boolean add(Object object)
```
    Deprecated.
    
    Adds an object to this heap. Same as insert(Object).
    
    Specified by:
    
    add in interface Collection
    
    Overrides:
    
    add in class AbstractCollection
    
    Parameters:
    object - the object to add
    
    Returns:
    true, always
  - get
```
public 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 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 Collection
    
    Specified by:
    
    size in class AbstractCollection
    
    Returns:
    the number of elements in this heap

Class BinaryHeap

Constructor Summary

Method Summary

Methods inherited from class java.util.AbstractCollection

Methods inherited from class java.lang.Object

Methods inherited from interface java.util.Collection

Constructor Detail

BinaryHeap

BinaryHeap

BinaryHeap

BinaryHeap

BinaryHeap

BinaryHeap

BinaryHeap

BinaryHeap

Method Detail

clear

isEmpty

isFull

insert

peek

pop

percolateDownMinHeap

percolateDownMaxHeap

percolateUpMinHeap

percolateUpMinHeap

percolateUpMaxHeap

percolateUpMaxHeap

grow

toString

iterator

add

get

remove

size