Package com.google.common.collect
Class MinMaxPriorityQueue.Heap
java.lang.Object
com.google.common.collect.MinMaxPriorityQueue.Heap
- Enclosing class:
- MinMaxPriorityQueue<E>
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).
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) voidBubbles a value fromindexup the appropriate heap if required.(package private) intbubbleUpAlternatingLevels(int index, E x) Bubbles a value fromindexup the levels of this heap, and returns the index the element ended up at.(package private) intcompareElements(int a, int b) (package private) intCrosses an element over to the opposite heap by moving it one level down (or up if there are no elements below it).(package private) intcrossOverUp(int index, E x) Moves an element one level up from a min level to a max level (or vice versa).(package private) intfillHoleAt(int index) Fills the hole atindexby moving in the least of its grandchildren to this position, then recursively filling the new hole created.(package private) intfindMin(int index, int len) Returns the index of minimum value betweenindexandindex + len, or-1ifindexis greater thansize.(package private) intfindMinChild(int index) Returns the minimum child or-1if no child exists.(package private) intfindMinGrandChild(int index) Returns the minimum grand child or -1 if no grand child exists.private intgetGrandparentIndex(int i) private intgetLeftChildIndex(int i) private intgetParentIndex(int i) private intgetRightChildIndex(int i) (package private) intswapWithConceptuallyLastElement(E actualLastElement) SwapactualLastElementwith the conceptually correct last element of the heap.(package private) MinMaxPriorityQueue.MoveDesc<E>tryCrossOverAndBubbleUp(int removeIndex, int vacated, E toTrickle) Tries to movetoTricklefrom a min to a max level and bubble up there.private booleanverifyIndex(int i)
-
Field Details
-
ordering
-
otherHeap
MinMaxPriorityQueue<E>.Heap otherHeap
-
-
Constructor Details
-
Heap
-
-
Method Details
-
compareElements
int compareElements(int a, int b) -
tryCrossOverAndBubbleUp
@CheckForNull MinMaxPriorityQueue.MoveDesc<E> tryCrossOverAndBubbleUp(int removeIndex, int vacated, E toTrickle) Tries to movetoTricklefrom a min to a max level and bubble up there. If it moved beforeremoveIndexthis method returns a pair as described inMinMaxPriorityQueue.removeAt(int). -
bubbleUp
Bubbles a value fromindexup the appropriate heap if required. -
bubbleUpAlternatingLevels
Bubbles a value fromindexup 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 betweenindexandindex + len, or-1ifindexis greater thansize. -
findMinChild
int findMinChild(int index) Returns the minimum child or-1if no child exists. -
findMinGrandChild
int findMinGrandChild(int index) Returns the minimum grand child or -1 if no grand child exists. -
crossOverUp
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
SwapactualLastElementwith the conceptually correct last element of the heap. Returns the index thatactualLastElementnow 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
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 atindexby 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)
-