Lines Matching defs:heap
62 * <a href="http://portal.acm.org/citation.cfm?id=6621">min-max heap</a>
64 * it stores elements in a single array, as compact as the traditional heap data
219 private final Heap minHeap;
220 private final Heap maxHeap;
228 this.minHeap = new Heap(ordering);
229 this.maxHeap = new Heap(ordering.reverse());
277 // Adds the element to the end of the heap and bubbles it up to the correct
371 * <p>Occasionally, in order to maintain the heap invariant, it must swap a
374 * first one is the element that was previously at the end of the heap and is
410 Heap heap = heapForIndex(index);
412 // with the last element of the heap, toTrickle.
413 // Since the last element of the heap is from the bottom level, we
418 int vacated = heap.fillHoleAt(index);
420 int bubbledTo = heap.bubbleUpAlternatingLevels(vacated, toTrickle);
425 return heap.tryCrossOverAndBubbleUp(index, vacated, toTrickle);
453 private Heap heapForIndex(int i) {
467 * Returns {@code true} if the MinMax heap structure holds. This is only used
482 * Each instance of MinMaxPriortyQueue encapsulates two instances of Heap:
483 * a min-heap and a max-heap. Conceptually, these might each have their own
485 * alternate heap levels in the same array (MMPQ.queue).
487 private class Heap {
489 Heap otherHeap;
491 Heap(Ordering<E> ordering) {
523 // bubble it up the opposite heap
533 * Bubbles a value from {@code index} up the appropriate heap if required.
538 Heap heap;
540 heap = this;
543 heap = otherHeap;
545 heap.bubbleUpAlternatingLevels(index, x);
549 * Bubbles a value from {@code index} up the levels of this heap, and
618 // Since the end of the array is actually the middle of the heap,
642 * Returns the conceptually correct last element of the heap.
669 * Crosses an element over to the opposite heap by moving it one level down
