private class MinMaxPriorityQueue.Heap
extends java.lang.Object
Modifier and Type | Field and Description |
---|---|
(package private) Ordering<E> |
ordering |
(package private) MinMaxPriorityQueue.Heap |
otherHeap |
Modifier and Type | Method and 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) |
MinMaxPriorityQueue.Heap otherHeap
int compareElements(int a, int b)
MinMaxPriorityQueue.MoveDesc<E> tryCrossOverAndBubbleUp(int removeIndex, int vacated, E toTrickle)
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)
.void bubbleUp(int index, E x)
index
up the appropriate heap if required.int bubbleUpAlternatingLevels(int index, E x)
index
up the levels of this heap, and returns the index the
element ended up at.int findMin(int index, int len)
index
and index + len
, or -1
if index
is greater than size
.int findMinChild(int index)
-1
if no child exists.int findMinGrandChild(int index)
int crossOverUp(int index, E x)
int swapWithConceptuallyLastElement(E actualLastElement)
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.
int crossOver(int index, E x)
Returns the new position of the element.
int fillHoleAt(int index)
index
by moving in the least of its grandchildren to this position,
then recursively filling the new hole created.private boolean verifyIndex(int i)
private int getLeftChildIndex(int i)
private int getRightChildIndex(int i)
private int getParentIndex(int i)
private int getGrandparentIndex(int i)