Class MinMaxPriorityQueue.Heap

  • Enclosing class:
    MinMaxPriorityQueue<E>

    private class MinMaxPriorityQueue.Heap
    extends java.lang.Object
    Each instance of MinMaxPriortyQueue 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).
    • Constructor Summary

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

      All Methods Instance Methods Concrete Methods 
      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 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.
      (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 getGrandparentIndex​(int i)  
      private int getLeftChildIndex​(int i)  
      private int getParentIndex​(int i)  
      private int getRightChildIndex​(int i)  
      (package private) int swapWithConceptuallyLastElement​(E actualLastElement)
      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
    • Constructor Detail

    • Method Detail

      • 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 uncle node could be smaller, which would corrupt the invariant if this element becomes the new parent of the uncle. In that case, we first switch the last element with its uncle, 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)