Package com.google.common.collect
Class MinMaxPriorityQueue.Heap
java.lang.Object
com.google.common.collect.MinMaxPriorityQueue.Heap
- Enclosing class:
MinMaxPriorityQueue<E>
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 -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) void
Bubbles a value fromindex
up the appropriate heap if required.(package private) int
bubbleUpAlternatingLevels
(int index, E x) Bubbles a value fromindex
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
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 atindex
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 betweenindex
andindex + len
, or-1
ifindex
is greater thansize
.(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) SwapactualLastElement
with the conceptually correct last element of the heap.(package private) MinMaxPriorityQueue.MoveDesc
<E> tryCrossOverAndBubbleUp
(int removeIndex, int vacated, E toTrickle) Tries to movetoTrickle
from a min to a max level and bubble up there.private boolean
verifyIndex
(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 movetoTrickle
from a min to a max level and bubble up there. If it moved beforeremoveIndex
this method returns a pair as described inMinMaxPriorityQueue.removeAt(int)
. -
bubbleUp
Bubbles a value fromindex
up the appropriate heap if required. -
bubbleUpAlternatingLevels
Bubbles a value fromindex
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 betweenindex
andindex + len
, or-1
ifindex
is greater thansize
. -
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
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
SwapactualLastElement
with the conceptually correct last element of the heap. Returns the index thatactualLastElement
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
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 atindex
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)
-