Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.apache.commons.collections
Class BinaryHeap

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

All Implemented Interfaces:
  Buffer, Collection, 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: 1.24 $ $Date: 2004/02/18 01:15:42 $
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, 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
`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 `PriorityQueue`
  Overrides:
    `clear` in class `AbstractCollection`

### isEmpty

    public boolean isEmpty()

  Deprecated.
  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()

  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 `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

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2001-2004 Apache Software Foundation. All Rights Reserved.