Class MinMaxPriorityQueue.Heap

java.lang.Object
com.google.common.collect.MinMaxPriorityQueue.Heap
Enclosing class:
MinMaxPriorityQueue<E>

class MinMaxPriorityQueue.Heap extends Object
Each instance of MinMaxPriorityQueue encapsulates two instances of Heap: a min-heap and a max-heap. Conceptually, these might each have their own array for storage, but for efficiency's sake they are stored interleaved on alternate heap levels in the same array (MMPQ.queue).
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    (package private) final Ordering<E>
     
    (package private) MinMaxPriorityQueue<E>.Heap
     
  • Constructor Summary

    Constructors
    Constructor
    Description
    Heap(Ordering<E> ordering)
     
  • Method Summary

    Modifier and Type
    Method
    Description
    (package private) void
    bubbleUp(int index, E x)
    Bubbles a value from index up the appropriate heap if required.
    (package private) int
    Bubbles a value from index up the levels of this heap, and returns the index the element ended up at.
    (package private) int
    compareElements(int a, int b)
     
    (package private) int
    crossOver(int index, E x)
    Crosses an element over to the opposite heap by moving it one level down (or up if there are no elements below it).
    (package private) int
    crossOverUp(int index, E x)
    Moves an element one level up from a min level to a max level (or vice versa).
    (package private) int
    fillHoleAt(int index)
    Fills the hole at index by moving in the least of its grandchildren to this position, then recursively filling the new hole created.
    (package private) int
    findMin(int index, int len)
    Returns the index of minimum value between index and index + len, or -1 if index is greater than size.
    (package private) int
    findMinChild(int index)
    Returns the minimum child or -1 if no child exists.
    (package private) int
    findMinGrandChild(int index)
    Returns the minimum grand child or -1 if no grand child exists.
    private int
     
    private int
     
    private int
     
    private int
     
    (package private) int
    Swap actualLastElement with the conceptually correct last element of the heap.
    (package private) MinMaxPriorityQueue.MoveDesc<E>
    tryCrossOverAndBubbleUp(int removeIndex, int vacated, E toTrickle)
    Tries to move toTrickle from a min to a max level and bubble up there.
    private boolean
    verifyIndex(int i)
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

  • Constructor Details

  • Method Details

    • compareElements

      int compareElements(int a, int b)
    • tryCrossOverAndBubbleUp

      @CheckForNull MinMaxPriorityQueue.MoveDesc<E> tryCrossOverAndBubbleUp(int removeIndex, int vacated, E toTrickle)
      Tries to move toTrickle from a min to a max level and bubble up there. If it moved before removeIndex this method returns a pair as described in MinMaxPriorityQueue.removeAt(int).
    • bubbleUp

      void bubbleUp(int index, E x)
      Bubbles a value from index up the appropriate heap if required.
    • bubbleUpAlternatingLevels

      int bubbleUpAlternatingLevels(int index, E x)
      Bubbles a value from index up the levels of this heap, and returns the index the element ended up at.
    • findMin

      int findMin(int index, int len)
      Returns the index of minimum value between index and index + len, or -1 if index is greater than size.
    • findMinChild

      int findMinChild(int index)
      Returns the minimum child or -1 if no child exists.
    • findMinGrandChild

      int findMinGrandChild(int index)
      Returns the minimum grand child or -1 if no grand child exists.
    • crossOverUp

      int crossOverUp(int index, E x)
      Moves an element one level up from a min level to a max level (or vice versa). Returns the new position of the element.
    • swapWithConceptuallyLastElement

      int swapWithConceptuallyLastElement(E actualLastElement)
      Swap actualLastElement with the conceptually correct last element of the heap. Returns the index that actualLastElement now resides in.

      Since the last element of the array is actually in the middle of the sorted structure, a childless aunt node could be smaller, which would corrupt the invariant if this element becomes the new parent of the aunt node. In that case, we first switch the last element with its aunt node, before returning.

    • crossOver

      int crossOver(int index, E x)
      Crosses an element over to the opposite heap by moving it one level down (or up if there are no elements below it).

      Returns the new position of the element.

    • fillHoleAt

      int fillHoleAt(int index)
      Fills the hole at index by moving in the least of its grandchildren to this position, then recursively filling the new hole created.
      Returns:
      the position of the new hole (where the lowest grandchild moved from, that had no grandchild to replace it)
    • verifyIndex

      private boolean verifyIndex(int i)
    • getLeftChildIndex

      private int getLeftChildIndex(int i)
    • getRightChildIndex

      private int getRightChildIndex(int i)
    • getParentIndex

      private int getParentIndex(int i)
    • getGrandparentIndex

      private int getGrandparentIndex(int i)