Package edu.uci.ics.jung.algorithms.util

Class MapBinaryHeap<T>

  • All Implemented Interfaces:
    java.lang.Iterable<T>, java.util.Collection<T>, java.util.Queue<T>
    public class MapBinaryHeap<T>
extends java.util.AbstractCollection<T>
implements java.util.Queue<T>
    An array-based binary heap implementation of a priority queue, which also provides efficient update() and contains operations. It contains extra infrastructure (a hash table) to keep track of the position of each element in the array; thus, if the key value of an element changes, it may be "resubmitted" to the heap via update so that the heap can reposition it efficiently, as necessary.
    Author:
    Joshua O'Madadhain

    • Constructor Summary

      Constructors 
      Constructor Description
      MapBinaryHeap()
      Creates a MapBinaryHeap whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.
      MapBinaryHeap​(java.util.Collection<T> c)
      Creates a MapBinaryHeap based on the specified collection whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.
      MapBinaryHeap​(java.util.Collection<T> c, java.util.Comparator<T> comp)
      Creates a MapBinaryHeap based on the specified collection whose heap ordering is based on the ordering of the elements specified by c.
      MapBinaryHeap​(java.util.Comparator<T> comp)
      Creates a MapBinaryHeap whose heap ordering is based on the ordering of the elements specified by comp.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(T o)
      Inserts o into this collection.
      void clear()  
      boolean contains​(java.lang.Object o)  
      T element()  
      boolean isEmpty()
      Returns true if this collection contains no elements, and false otherwise.
      java.util.Iterator<T> iterator()
      Returns an Iterator that does not support modification of the heap.
      boolean offer​(T o)  
      T peek()
      Returns the element at the top of the heap; does not alter the heap.
      T poll()  
      T remove()  
      boolean remove​(java.lang.Object o)
      This data structure does not support the removal of arbitrary elements.
      boolean removeAll​(java.util.Collection<?> c)
      This data structure does not support the removal of arbitrary elements.
      boolean retainAll​(java.util.Collection<?> c)
      This data structure does not support the removal of arbitrary elements.
      int size()  
      void update​(T o)
      Informs the heap that this object's internal key value has been updated, and that its place in the heap may need to be shifted (up or down).

      • Methods inherited from class java.util.AbstractCollection

        addAll, containsAll, toArray, toArray, toString

      • 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, containsAll, equals, hashCode, parallelStream, removeIf, spliterator, stream, toArray, toArray, toArray

      • Methods inherited from interface java.lang.Iterable

        forEach

    • Constructor Detail

      • MapBinaryHeap

        public MapBinaryHeap​(java.util.Comparator<T> comp)
        Creates a MapBinaryHeap whose heap ordering is based on the ordering of the elements specified by comp.
        Parameters:
        comp - the comparator to use to order elements in the heap

      • MapBinaryHeap

        public MapBinaryHeap()
        Creates a MapBinaryHeap whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.

      • MapBinaryHeap

        public MapBinaryHeap​(java.util.Collection<T> c)
        Creates a MapBinaryHeap based on the specified collection whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.
        Parameters:
        c - the collection of Comparable elements to add to the heap

      • MapBinaryHeap

        public MapBinaryHeap​(java.util.Collection<T> c,
                     java.util.Comparator<T> comp)
        Creates a MapBinaryHeap based on the specified collection whose heap ordering is based on the ordering of the elements specified by c.
        Parameters:
        c - the collection of elements to add to the heap
        comp - the comparator to use for items in c

    • Method Detail

      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Collection<T>
        Overrides:
        clear in class java.util.AbstractCollection<T>
        See Also:
        Collection.clear()

      • add

        public boolean add​(T o)
        Inserts o into this collection.
        Specified by:
        add in interface java.util.Collection<T>
        Specified by:
        add in interface java.util.Queue<T>
        Overrides:
        add in class java.util.AbstractCollection<T>

      • isEmpty

        public boolean isEmpty()
        Returns true if this collection contains no elements, and false otherwise.
        Specified by:
        isEmpty in interface java.util.Collection<T>
        Overrides:
        isEmpty in class java.util.AbstractCollection<T>

      • peek

        public T peek()
        Returns the element at the top of the heap; does not alter the heap.
        Specified by:
        peek in interface java.util.Queue<T>

      • size

        public int size()
        Specified by:
        size in interface java.util.Collection<T>
        Specified by:
        size in class java.util.AbstractCollection<T>
        Returns:
        the size of this heap

      • update

        public void update​(T o)
        Informs the heap that this object's internal key value has been updated, and that its place in the heap may need to be shifted (up or down).
        Parameters:
        o - the object whose key value has been updated

      • contains

        public boolean contains​(java.lang.Object o)
        Specified by:
        contains in interface java.util.Collection<T>
        Overrides:
        contains in class java.util.AbstractCollection<T>

      • iterator

        public java.util.Iterator<T> iterator()
        Returns an Iterator that does not support modification of the heap.
        Specified by:
        iterator in interface java.util.Collection<T>
        Specified by:
        iterator in interface java.lang.Iterable<T>
        Specified by:
        iterator in class java.util.AbstractCollection<T>

      • remove

        public boolean remove​(java.lang.Object o)
        This data structure does not support the removal of arbitrary elements.
        Specified by:
        remove in interface java.util.Collection<T>
        Overrides:
        remove in class java.util.AbstractCollection<T>

      • removeAll

        public boolean removeAll​(java.util.Collection<?> c)
        This data structure does not support the removal of arbitrary elements.
        Specified by:
        removeAll in interface java.util.Collection<T>
        Overrides:
        removeAll in class java.util.AbstractCollection<T>

      • retainAll

        public boolean retainAll​(java.util.Collection<?> c)
        This data structure does not support the removal of arbitrary elements.
        Specified by:
        retainAll in interface java.util.Collection<T>
        Overrides:
        retainAll in class java.util.AbstractCollection<T>

      • element

        public T element()
          throws java.util.NoSuchElementException
        Specified by:
        element in interface java.util.Queue<T>
        Throws:
        java.util.NoSuchElementException

      • offer

        public boolean offer​(T o)
        Specified by:
        offer in interface java.util.Queue<T>

      • poll

        public T poll()
        Specified by:
        poll in interface java.util.Queue<T>

      • remove

        public T remove()
        Specified by:
        remove in interface java.util.Queue<T>