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.
|
(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 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 getCorrectLastElement(E actualLastElement)
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)
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)