Class MapBinaryHeap<T>

java.lang.Object
java.util.AbstractCollection<T>
edu.uci.ics.jung.algorithms.util.MapBinaryHeap<T>
All Implemented Interfaces:
Iterable<T>, Collection<T>, Queue<T>
public class MapBinaryHeap<T> extends AbstractCollection<T> implements 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 Comparator<T>
    comp
     
    private Vector<T>
    heap
     
    private Map<T,Integer>
    object_indices
     
    private static final 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(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(Collection<T> c, 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(Comparator<T> comp)
    Creates a MapBinaryHeap whose heap ordering is based on the ordering of the elements specified by comp.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(T o)
    Inserts o into this collection.
    void
    clear()
     
    boolean
    contains(Object o)
     
    T
    element()
     
    private void
    initialize(Comparator<T> comp)
     
    boolean
    isEmpty()
    Returns true if this collection contains no elements, and false otherwise.
    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(Object o)
    This data structure does not support the removal of arbitrary elements.
    boolean
    removeAll(Collection<?> c)
    This data structure does not support the removal of arbitrary elements.
    boolean
    retainAll(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 AbstractCollection

    addAll, containsAll, toArray, toArray, toString

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

    Methods inherited from interface Collection

    addAll, containsAll, equals, hashCode, parallelStream, removeIf, spliterator, stream, toArray, toArray, toArray

    Methods inherited from interface Iterable

    forEach

  • Field Details

  • Constructor Details

    • MapBinaryHeap

      public MapBinaryHeap(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(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(Collection<T> c, 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 Details

    • initialize

      private void initialize(Comparator<T> comp)

    • clear

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

    • add

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

    • isEmpty

      public boolean isEmpty()
      Returns true if this collection contains no elements, and false otherwise.
      Specified by:
      isEmpty in interface Collection<T>
      Overrides:
      isEmpty in class 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 Queue<T>

    • size

      public int size()
      Specified by:
      size in interface Collection<T>
      Specified by:
      size in class 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(Object o)
      Specified by:
      contains in interface Collection<T>
      Overrides:
      contains in class 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 Iterator<T> iterator()
      Returns an Iterator that does not support modification of the heap.
      Specified by:
      iterator in interface Collection<T>
      Specified by:
      iterator in interface Iterable<T>
      Specified by:
      iterator in class AbstractCollection<T>

    • remove

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

    • removeAll

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

    • retainAll

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

    • element

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

    • offer

      public boolean offer(T o)
      Specified by:
      offer in interface Queue<T>

    • poll

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

    • remove

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