org.apache.commons.collections

## Class BinaryHeap

- 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: 646777 $ $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

Copyright © 2001–2015 The Apache Software Foundation. All rights reserved.