Package com.google.common.collect
Class MinMaxPriorityQueue.Heap
- java.lang.Object
-
- com.google.common.collect.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).
-
-
Field Summary
Fields Modifier and Type Field Description (package private) Ordering<E>
ordering
(package private) MinMaxPriorityQueue.Heap
otherHeap
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) void
bubbleUp(int index, E x)
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
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 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.(package private) int
getCorrectLastElement(E actualLastElement)
Returns the conceptually correct last element of the heap.private int
getGrandparentIndex(int i)
private int
getLeftChildIndex(int i)
private int
getParentIndex(int i)
private int
getRightChildIndex(int i)
(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 Detail
-
otherHeap
MinMaxPriorityQueue.Heap otherHeap
-
-
Method Detail
-
compareElements
int compareElements(int a, int b)
-
tryCrossOverAndBubbleUp
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
void bubbleUp(int index, E x)
Bubbles a value fromindex
up the appropriate heap if required.
-
bubbleUpAlternatingLevels
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.
-
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
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.
-
getCorrectLastElement
int getCorrectLastElement(E actualLastElement)
Returns the conceptually correct last element of the heap.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 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)
-
-