Class BinaryHeap

  • All Implemented Interfaces:
    java.lang.Iterable, java.util.Collection, Buffer, PriorityQueue

    public final class BinaryHeap
    extends java.util.AbstractCollection
    implements PriorityQueue, Buffer
    Deprecated.
    Replaced by PriorityBuffer in buffer subpackage. Due to be removed in v4.0.
    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) $
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static int DEFAULT_CAPACITY
      Deprecated.
      The default capacity for a binary heap.
      (package private) java.util.Comparator m_comparator
      Deprecated.
      The comparator used to order the elements
      (package private) java.lang.Object[] m_elements
      Deprecated.
      The elements in this heap.
      (package private) boolean m_isMinHeap
      Deprecated.
      If true, the first element as determined by the sort order will be returned.
      (package private) int m_size
      Deprecated.
      The number of elements currently in this heap.
    • Constructor Summary

      Constructors 
      Constructor Description
      BinaryHeap()
      Deprecated.
      Constructs a new minimum binary heap.
      BinaryHeap​(boolean isMinHeap)
      Deprecated.
      Constructs a new minimum or maximum binary heap
      BinaryHeap​(boolean isMinHeap, java.util.Comparator comparator)
      Deprecated.
      Constructs a new BinaryHeap.
      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, java.util.Comparator comparator)
      Deprecated.
      Constructs a new BinaryHeap.
      BinaryHeap​(int capacity, java.util.Comparator comparator)
      Deprecated.
      Constructs a new BinaryHeap.
      BinaryHeap​(java.util.Comparator comparator)
      Deprecated.
      Constructs a new BinaryHeap that will use the given comparator to order its elements.
    • Method Summary

      All Methods Instance Methods Concrete Methods Deprecated Methods 
      Modifier and Type Method Description
      boolean add​(java.lang.Object object)
      Deprecated.
      Adds an object to this heap.
      void clear()
      Deprecated.
      Clears all elements from queue.
      private int compare​(java.lang.Object a, java.lang.Object b)
      Deprecated.
      Compares two objects using the comparator if specified, or the natural order otherwise.
      java.lang.Object get()
      Deprecated.
      Returns the priority element.
      protected void grow()
      Deprecated.
      Increases the size of the heap to support additional elements
      void insert​(java.lang.Object element)
      Deprecated.
      Inserts an element into queue.
      boolean isEmpty()
      Deprecated.
      Tests if queue is empty.
      boolean isFull()
      Deprecated.
      Tests if queue is full.
      java.util.Iterator iterator()
      Deprecated.
      Returns an iterator over this heap's elements.
      java.lang.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​(java.lang.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​(java.lang.Object element)
      Deprecated.
      Percolates a new element up heap from the bottom.
      java.lang.Object pop()
      Deprecated.
      Returns the element on top of heap and remove it.
      java.lang.Object remove()
      Deprecated.
      Removes the priority element.
      int size()
      Deprecated.
      Returns the number of elements in this heap.
      java.lang.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, parallelStream, remove, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray, toArray
      • Methods inherited from interface java.lang.Iterable

        forEach
    • Field Detail

      • DEFAULT_CAPACITY

        private static final int DEFAULT_CAPACITY
        Deprecated.
        The default capacity for a binary heap.
        See Also:
        Constant Field Values
      • m_size

        int m_size
        Deprecated.
        The number of elements currently in this heap.
      • m_elements

        java.lang.Object[] m_elements
        Deprecated.
        The elements in this heap.
      • m_isMinHeap

        boolean m_isMinHeap
        Deprecated.
        If true, the first element as determined by the sort order will be returned. If false, the last element as determined by the sort order will be returned.
      • m_comparator

        java.util.Comparator m_comparator
        Deprecated.
        The comparator used to order the elements
    • Constructor Detail

      • BinaryHeap

        public BinaryHeap()
        Deprecated.
        Constructs a new minimum binary heap.
      • BinaryHeap

        public BinaryHeap​(java.util.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:
        java.lang.IllegalArgumentException - if capacity is <= 0
      • BinaryHeap

        public BinaryHeap​(int capacity,
                          java.util.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:
        java.lang.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,
                          java.util.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:
        java.lang.IllegalArgumentException - if capacity is <= 0
      • BinaryHeap

        public BinaryHeap​(int capacity,
                          boolean isMinHeap,
                          java.util.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:
        java.lang.IllegalArgumentException - if capacity is <= 0
    • Method Detail

      • clear

        public void clear()
        Deprecated.
        Clears all elements from queue.
        Specified by:
        clear in interface java.util.Collection
        Specified by:
        clear in interface PriorityQueue
        Overrides:
        clear in class java.util.AbstractCollection
      • isEmpty

        public boolean isEmpty()
        Deprecated.
        Tests if queue is empty.
        Specified by:
        isEmpty in interface java.util.Collection
        Specified by:
        isEmpty in interface PriorityQueue
        Overrides:
        isEmpty in class java.util.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​(java.lang.Object element)
        Deprecated.
        Inserts an element into queue.
        Specified by:
        insert in interface PriorityQueue
        Parameters:
        element - the element to be inserted
      • peek

        public java.lang.Object peek()
                              throws java.util.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:
        java.util.NoSuchElementException - if isEmpty() == true
      • pop

        public java.lang.Object pop()
                             throws java.util.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:
        java.util.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​(java.lang.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​(java.lang.Object element)
        Deprecated.
        Percolates a new element up heap from the bottom.

        Assume it is a maximum heap.

        Parameters:
        element - the element
      • compare

        private int compare​(java.lang.Object a,
                            java.lang.Object b)
        Deprecated.
        Compares two objects using the comparator if specified, or the natural order otherwise.
        Parameters:
        a - the first object
        b - the second object
        Returns:
        -ve if a less than b, 0 if they are equal, +ve if a greater than b
      • grow

        protected void grow()
        Deprecated.
        Increases the size of the heap to support additional elements
      • toString

        public java.lang.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 java.util.AbstractCollection
        Returns:
        a string representation of this heap
      • iterator

        public java.util.Iterator iterator()
        Deprecated.
        Returns an iterator over this heap's elements.
        Specified by:
        iterator in interface java.util.Collection
        Specified by:
        iterator in interface java.lang.Iterable
        Specified by:
        iterator in class java.util.AbstractCollection
        Returns:
        an iterator over this heap's elements
      • add

        public boolean add​(java.lang.Object object)
        Deprecated.
        Adds an object to this heap. Same as insert(Object).
        Specified by:
        add in interface java.util.Collection
        Overrides:
        add in class java.util.AbstractCollection
        Parameters:
        object - the object to add
        Returns:
        true, always
      • get

        public java.lang.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 java.lang.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 java.util.Collection
        Specified by:
        size in class java.util.AbstractCollection
        Returns:
        the number of elements in this heap