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.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private class  MapBinaryHeap.ComparableComparator
      Comparator used if none is specified in the constructor.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.Comparator<T> comp  
      private java.util.Vector<T> heap  
      private java.util.Map<T,​java.lang.Integer> object_indices  
      private static int TOP  

    • 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()  
      private void initialize​(java.util.Comparator<T> comp)  
      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.
      private int lChild​(int i)
      Returns the index of the left child of the element at index i of the heap.
      boolean offer​(T o)  
      private int parent​(int i)
      Returns the index of the parent of the element at index i of the heap.
      T peek()
      Returns the element at the top of the heap; does not alter the heap.
      private void percolateDown​(int cur)
      Moves the element at position cur closer to the bottom of the heap, or returns if no further motion is necessary.
      private int percolateUp​(int cur, T o)
      Moves the element o at position cur as high as it can go in the heap.
      T poll()  
      private int rChild​(int i)
      Returns the index of the right child of the element at index i of the heap.
      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()  
      private void swap​(int i, int j)
      Swaps the positions of the elements at indices i and j of the heap.
      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

    • Field Detail

      • heap

        private java.util.Vector<T> heap

      • object_indices

        private java.util.Map<T,​java.lang.Integer> object_indices

      • comp

        private java.util.Comparator<T> comp

    • 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

      • initialize

        private void initialize​(java.util.Comparator<T> comp)

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

      • percolateDown

        private void percolateDown​(int cur)
        Moves the element at position cur closer to the bottom of the heap, or returns if no further motion is necessary. Calls itself recursively if further motion is possible.

      • percolateUp

        private int percolateUp​(int cur,
                        T o)
        Moves the element o at position cur as high as it can go in the heap. Returns the new position of the element in the heap.

      • lChild

        private int lChild​(int i)
        Returns the index of the left child of the element at index i of the heap.
        Parameters:
        i -
        Returns:
        the index of the left child of the element at index i of the heap

      • rChild

        private int rChild​(int i)
        Returns the index of the right child of the element at index i of the heap.
        Parameters:
        i -
        Returns:
        the index of the right child of the element at index i of the heap

      • parent

        private int parent​(int i)
        Returns the index of the parent of the element at index i of the heap.
        Parameters:
        i -
        Returns:
        the index of the parent of the element at index i of the heap

      • swap

        private void swap​(int i,
                  int j)
        Swaps the positions of the elements at indices i and j of the heap.
        Parameters:
        i -
        j -

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