https://github.com/google/guava/guava: Guava is a suite of core and expanded libraries that include utility classes, google's collections, io classes, and much much more. 
/*
 * Copyright (C) 2010 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkPositionIndex;
import static com.google.common.base.Preconditions.checkState;
import static com.google.common.collect.CollectPreconditions.checkRemove;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.math.IntMath;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.j2objc.annotations.Weak;
import com.google.j2objc.annotations.WeakOuter;
import java.util.AbstractQueue;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;
import org.checkerframework.checker.nullness.qual.MonotonicNonNull;
import org.checkerframework.checker.nullness.qual.Nullable;


A double-ended priority queue, which provides constant-time access to both its least element and
its greatest element, as determined by the queue's specified comparator. If no comparator is
given at creation time, the natural order of elements is used. If no maximum size is given at
creation time, the queue is unbounded.

Usage example:


MinMaxPriorityQueue<User> users = MinMaxPriorityQueue.orderedBy(userComparator)
    .maximumSize(1000)
    .create();



As a Queue it functions exactly as a PriorityQueue: its head element -- the implicit target of the methods peek(), poll() and AbstractQueue.remove() -- is defined as the least element in the queue according to the queue's comparator. But unlike a regular priority queue, the methods peekLast, pollLast and removeLast are also provided, to act on the greatest element in the queue instead.

A min-max priority queue can be configured with a maximum size. If so, each time the size of
the queue exceeds that value, the queue automatically removes its greatest element according to
its comparator (which might be the element that was just added). This is different from
conventional bounded queues, which either block or reject new elements when full.

This implementation is based on the min-max heap developed by Atkinson, et al. Unlike many other double-ended priority queues, it stores elements in a single array, as compact as the traditional heap data structure used in PriorityQueue. 
This class is not thread-safe, and does not accept null elements.

Performance notes:



Author:Sverre Sundsdal, Torbjorn Gannholm
Since:8.0
/**
 * A double-ended priority queue, which provides constant-time access to both its least element and
 * its greatest element, as determined by the queue's specified comparator. If no comparator is
 * given at creation time, the natural order of elements is used. If no maximum size is given at
 * creation time, the queue is unbounded.
 *
 * <p>Usage example:
 *
 * <pre>{@code
 * MinMaxPriorityQueue<User> users = MinMaxPriorityQueue.orderedBy(userComparator)
 *     .maximumSize(1000)
 *     .create();
 * }</pre>
 *
 * <p>As a {@link Queue} it functions exactly as a {@link PriorityQueue}: its head element -- the
 * implicit target of the methods {@link #peek()}, {@link #poll()} and {@link #remove()} -- is
 * defined as the <i>least</i> element in the queue according to the queue's comparator. But unlike
 * a regular priority queue, the methods {@link #peekLast}, {@link #pollLast} and {@link
 * #removeLast} are also provided, to act on the <i>greatest</i> element in the queue instead.
 *
 * <p>A min-max priority queue can be configured with a maximum size. If so, each time the size of
 * the queue exceeds that value, the queue automatically removes its greatest element according to
 * its comparator (which might be the element that was just added). This is different from
 * conventional bounded queues, which either block or reject new elements when full.
 *
 * <p>This implementation is based on the <a
 * href="http://portal.acm.org/citation.cfm?id=6621">min-max heap</a> developed by Atkinson, et al.
 * Unlike many other double-ended priority queues, it stores elements in a single array, as compact
 * as the traditional heap data structure used in {@link PriorityQueue}.
 *
 * <p>This class is not thread-safe, and does not accept null elements.
 *
 * <p><i>Performance notes:</i>
 *
 * <ul>
 *   <li>If you only access one end of the queue, and do use a maximum size, this class will perform
 *       significantly worse than a {@code PriorityQueue} with manual eviction above the maximum
 *       size. In many cases {@link Ordering#leastOf} may work for your use case with significantly
 *       improved (and asymptotically superior) performance.
 *   <li>The retrieval operations {@link #peek}, {@link #peekFirst}, {@link #peekLast}, {@link
 *       #element}, and {@link #size} are constant-time.
 *   <li>The enqueuing and dequeuing operations ({@link #offer}, {@link #add}, and all the forms of
 *       {@link #poll} and {@link #remove()}) run in {@code O(log n) time}.
 *   <li>The {@link #remove(Object)} and {@link #contains} operations require linear ({@code O(n)})
 *       time.
 *   <li>If you only access one end of the queue, and don't use a maximum size, this class is
 *       functionally equivalent to {@link PriorityQueue}, but significantly slower.
 * </ul>
 *
 * @author Sverre Sundsdal
 * @author Torbjorn Gannholm
 * @since 8.0
 */
@Beta
@GwtCompatible
public final class MinMaxPriorityQueue<E> extends AbstractQueue<E> {

  
Creates a new min-max priority queue with default settings: natural order, no maximum size, no
initial contents, and an initial expected size of 11.

/**
   * Creates a new min-max priority queue with default settings: natural order, no maximum size, no
   * initial contents, and an initial expected size of 11.
   */
  public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create() {
    return new Builder<Comparable>(Ordering.natural()).create();
  }

  
Creates a new min-max priority queue using natural order, no maximum size, and initially
containing the given elements.

/**
   * Creates a new min-max priority queue using natural order, no maximum size, and initially
   * containing the given elements.
   */
  public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create(
      Iterable<? extends E> initialContents) {
    return new Builder<E>(Ordering.<E>natural()).create(initialContents);
  }

  
Creates and returns a new builder, configured to build MinMaxPriorityQueue instances that use comparator to determine the least and greatest elements. 
/**
   * Creates and returns a new builder, configured to build {@code MinMaxPriorityQueue} instances
   * that use {@code comparator} to determine the least and greatest elements.
   */
  public static <B> Builder<B> orderedBy(Comparator<B> comparator) {
    return new Builder<B>(comparator);
  }

  
Creates and returns a new builder, configured to build MinMaxPriorityQueue instances sized appropriately to hold expectedSize elements. 
/**
   * Creates and returns a new builder, configured to build {@code MinMaxPriorityQueue} instances
   * sized appropriately to hold {@code expectedSize} elements.
   */
  public static Builder<Comparable> expectedSize(int expectedSize) {
    return new Builder<Comparable>(Ordering.natural()).expectedSize(expectedSize);
  }

  
Creates and returns a new builder, configured to build MinMaxPriorityQueue instances that are limited to maximumSize elements. Each time a queue grows beyond this bound, it immediately removes its greatest element (according to its comparator), which might be the element that was just added. 
/**
   * Creates and returns a new builder, configured to build {@code MinMaxPriorityQueue} instances
   * that are limited to {@code maximumSize} elements. Each time a queue grows beyond this bound, it
   * immediately removes its greatest element (according to its comparator), which might be the
   * element that was just added.
   */
  public static Builder<Comparable> maximumSize(int maximumSize) {
    return new Builder<Comparable>(Ordering.natural()).maximumSize(maximumSize);
  }

  
The builder class used in creation of min-max priority queues. Instead of constructing one directly, use MinMaxPriorityQueue.orderedBy(Comparator<Object>), MinMaxPriorityQueue.expectedSize(int) or MinMaxPriorityQueue.maximumSize(int). 
Type parameters:
  • <B> – the upper bound on the eventual type that can be produced by this builder (for example, a Builder<Number> can produce a Queue<Number> or 
    Queue<Integer> but not a Queue<Object>).
Since:8.0
/**
   * The builder class used in creation of min-max priority queues. Instead of constructing one
   * directly, use {@link MinMaxPriorityQueue#orderedBy(Comparator)}, {@link
   * MinMaxPriorityQueue#expectedSize(int)} or {@link MinMaxPriorityQueue#maximumSize(int)}.
   *
   * @param <B> the upper bound on the eventual type that can be produced by this builder (for
   *     example, a {@code Builder<Number>} can produce a {@code Queue<Number>} or {@code
   *     Queue<Integer>} but not a {@code Queue<Object>}).
   * @since 8.0
   */
  @Beta
  public static final class Builder<B> {
    /*
     * TODO(kevinb): when the dust settles, see if we still need this or can
     * just default to DEFAULT_CAPACITY.
     */
    private static final int UNSET_EXPECTED_SIZE = -1;

    private final Comparator<B> comparator;
    private int expectedSize = UNSET_EXPECTED_SIZE;
    private int maximumSize = Integer.MAX_VALUE;

    private Builder(Comparator<B> comparator) {
      this.comparator = checkNotNull(comparator);
    }

    
Configures this builder to build min-max priority queues with an initial expected size of expectedSize. 
/**
     * Configures this builder to build min-max priority queues with an initial expected size of
     * {@code expectedSize}.
     */
    @CanIgnoreReturnValue
    public Builder<B> expectedSize(int expectedSize) {
      checkArgument(expectedSize >= 0);
      this.expectedSize = expectedSize;
      return this;
    }

    
Configures this builder to build MinMaxPriorityQueue instances that are limited to maximumSize elements. Each time a queue grows beyond this bound, it immediately removes its greatest element (according to its comparator), which might be the element that was just added. 
/**
     * Configures this builder to build {@code MinMaxPriorityQueue} instances that are limited to
     * {@code maximumSize} elements. Each time a queue grows beyond this bound, it immediately
     * removes its greatest element (according to its comparator), which might be the element that
     * was just added.
     */
    @CanIgnoreReturnValue
    public Builder<B> maximumSize(int maximumSize) {
      checkArgument(maximumSize > 0);
      this.maximumSize = maximumSize;
      return this;
    }

    
Builds a new min-max priority queue using the previously specified options, and having no
initial contents.

/**
     * Builds a new min-max priority queue using the previously specified options, and having no
     * initial contents.
     */
    public <T extends B> MinMaxPriorityQueue<T> create() {
      return create(Collections.<T>emptySet());
    }

    
Builds a new min-max priority queue using the previously specified options, and having the
given initial elements.

/**
     * Builds a new min-max priority queue using the previously specified options, and having the
     * given initial elements.
     */
    public <T extends B> MinMaxPriorityQueue<T> create(Iterable<? extends T> initialContents) {
      MinMaxPriorityQueue<T> queue =
          new MinMaxPriorityQueue<T>(
              this, initialQueueSize(expectedSize, maximumSize, initialContents));
      for (T element : initialContents) {
        queue.offer(element);
      }
      return queue;
    }

    @SuppressWarnings("unchecked") // safe "contravariant cast"
    private <T extends B> Ordering<T> ordering() {
      return Ordering.from((Comparator<T>) comparator);
    }
  }

  private final Heap minHeap;
  private final Heap maxHeap;
  @VisibleForTesting final int maximumSize;
  private Object[] queue;
  private int size;
  private int modCount;

  private MinMaxPriorityQueue(Builder<? super E> builder, int queueSize) {
    Ordering<E> ordering = builder.ordering();
    this.minHeap = new Heap(ordering);
    this.maxHeap = new Heap(ordering.reverse());
    minHeap.otherHeap = maxHeap;
    maxHeap.otherHeap = minHeap;

    this.maximumSize = builder.maximumSize;
    // TODO(kevinb): pad?
    this.queue = new Object[queueSize];
  }

  @Override
  public int size() {
    return size;
  }

  
Adds the given element to this queue. If this queue has a maximum size, after adding 
element the queue will automatically evict its greatest element (according to its comparator), which may be element itself. 
Returns:true always
/**
   * Adds the given element to this queue. If this queue has a maximum size, after adding {@code
   * element} the queue will automatically evict its greatest element (according to its comparator),
   * which may be {@code element} itself.
   *
   * @return {@code true} always
   */
  @CanIgnoreReturnValue
  @Override
  public boolean add(E element) {
    offer(element);
    return true;
  }

  @CanIgnoreReturnValue
  @Override
  public boolean addAll(Collection<? extends E> newElements) {
    boolean modified = false;
    for (E element : newElements) {
      offer(element);
      modified = true;
    }
    return modified;
  }

  
Adds the given element to this queue. If this queue has a maximum size, after adding 
element the queue will automatically evict its greatest element (according to its comparator), which may be element itself. 
/**
   * Adds the given element to this queue. If this queue has a maximum size, after adding {@code
   * element} the queue will automatically evict its greatest element (according to its comparator),
   * which may be {@code element} itself.
   */
  @CanIgnoreReturnValue
  @Override
  public boolean offer(E element) {
    checkNotNull(element);
    modCount++;
    int insertIndex = size++;

    growIfNeeded();

    // Adds the element to the end of the heap and bubbles it up to the correct
    // position.
    heapForIndex(insertIndex).bubbleUp(insertIndex, element);
    return size <= maximumSize || pollLast() != element;
  }

  @CanIgnoreReturnValue
  @Override
  public E poll() {
    return isEmpty() ? null : removeAndGet(0);
  }

  @SuppressWarnings("unchecked") // we must carefully only allow Es to get in
  E elementData(int index) {
    return (E) queue[index];
  }

  @Override
  public E peek() {
    return isEmpty() ? null : elementData(0);
  }

  
Returns the index of the max element. 
/** Returns the index of the max element. */
  private int getMaxElementIndex() {
    switch (size) {
      case 1:
        return 0; // The lone element in the queue is the maximum.
      case 2:
        return 1; // The lone element in the maxHeap is the maximum.
      default:
        // The max element must sit on the first level of the maxHeap. It is
        // actually the *lesser* of the two from the maxHeap's perspective.
        return (maxHeap.compareElements(1, 2) <= 0) ? 1 : 2;
    }
  }

  
Removes and returns the least element of this queue, or returns null if the queue is empty. 
/**
   * Removes and returns the least element of this queue, or returns {@code null} if the queue is
   * empty.
   */
  @CanIgnoreReturnValue
  public E pollFirst() {
    return poll();
  }

  
Removes and returns the least element of this queue.

Throws:
  • NoSuchElementException – if the queue is empty
/**
   * Removes and returns the least element of this queue.
   *
   * @throws NoSuchElementException if the queue is empty
   */
  @CanIgnoreReturnValue
  public E removeFirst() {
    return remove();
  }

  
Retrieves, but does not remove, the least element of this queue, or returns null if the queue is empty. 
/**
   * Retrieves, but does not remove, the least element of this queue, or returns {@code null} if the
   * queue is empty.
   */
  public E peekFirst() {
    return peek();
  }

  
Removes and returns the greatest element of this queue, or returns null if the queue is empty. 
/**
   * Removes and returns the greatest element of this queue, or returns {@code null} if the queue is
   * empty.
   */
  @CanIgnoreReturnValue
  public E pollLast() {
    return isEmpty() ? null : removeAndGet(getMaxElementIndex());
  }

  
Removes and returns the greatest element of this queue.

Throws:
  • NoSuchElementException – if the queue is empty
/**
   * Removes and returns the greatest element of this queue.
   *
   * @throws NoSuchElementException if the queue is empty
   */
  @CanIgnoreReturnValue
  public E removeLast() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    return removeAndGet(getMaxElementIndex());
  }

  
Retrieves, but does not remove, the greatest element of this queue, or returns null if the queue is empty. 
/**
   * Retrieves, but does not remove, the greatest element of this queue, or returns {@code null} if
   * the queue is empty.
   */
  public E peekLast() {
    return isEmpty() ? null : elementData(getMaxElementIndex());
  }

  
Removes the element at position index. 
Normally this method leaves the elements at up to index - 1, inclusive, untouched. Under these circumstances, it returns null. 
Occasionally, in order to maintain the heap invariant, it must swap a later element of the list with one before index. Under these circumstances it returns a pair of elements as a MoveDesc. The first one is the element that was previously at the end of the heap and is now at some position before index. The second element is the one that was swapped down to replace the element at index. This fact is used by iterator.remove so as to visit elements during a traversal once and only once. 
/**
   * Removes the element at position {@code index}.
   *
   * <p>Normally this method leaves the elements at up to {@code index - 1}, inclusive, untouched.
   * Under these circumstances, it returns {@code null}.
   *
   * <p>Occasionally, in order to maintain the heap invariant, it must swap a later element of the
   * list with one before {@code index}. Under these circumstances it returns a pair of elements as
   * a {@link MoveDesc}. The first one is the element that was previously at the end of the heap and
   * is now at some position before {@code index}. The second element is the one that was swapped
   * down to replace the element at {@code index}. This fact is used by iterator.remove so as to
   * visit elements during a traversal once and only once.
   */
  @VisibleForTesting
  @CanIgnoreReturnValue
  MoveDesc<E> removeAt(int index) {
    checkPositionIndex(index, size);
    modCount++;
    size--;
    if (size == index) {
      queue[size] = null;
      return null;
    }
    E actualLastElement = elementData(size);
    int lastElementAt = heapForIndex(size).swapWithConceptuallyLastElement(actualLastElement);
    if (lastElementAt == index) {
      // 'actualLastElement' is now at 'lastElementAt', and the element that was at 'lastElementAt'
      // is now at the end of queue. If that's the element we wanted to remove in the first place,
      // don't try to (incorrectly) trickle it. Instead, just delete it and we're done.
      queue[size] = null;
      return null;
    }
    E toTrickle = elementData(size);
    queue[size] = null;
    MoveDesc<E> changes = fillHole(index, toTrickle);
    if (lastElementAt < index) {
      // Last element is moved to before index, swapped with trickled element.
      if (changes == null) {
        // The trickled element is still after index.
        return new MoveDesc<E>(actualLastElement, toTrickle);
      } else {
        // The trickled element is back before index, but the replaced element
        // has now been moved after index.
        return new MoveDesc<E>(actualLastElement, changes.replaced);
      }
    }
    // Trickled element was after index to begin with, no adjustment needed.
    return changes;
  }

  private MoveDesc<E> fillHole(int index, E toTrickle) {
    Heap heap = heapForIndex(index);
    // We consider elementData(index) a "hole", and we want to fill it
    // with the last element of the heap, toTrickle.
    // Since the last element of the heap is from the bottom level, we
    // optimistically fill index position with elements from lower levels,
    // moving the hole down. In most cases this reduces the number of
    // comparisons with toTrickle, but in some cases we will need to bubble it
    // all the way up again.
    int vacated = heap.fillHoleAt(index);
    // Try to see if toTrickle can be bubbled up min levels.
    int bubbledTo = heap.bubbleUpAlternatingLevels(vacated, toTrickle);
    if (bubbledTo == vacated) {
      // Could not bubble toTrickle up min levels, try moving
      // it from min level to max level (or max to min level) and bubble up
      // there.
      return heap.tryCrossOverAndBubbleUp(index, vacated, toTrickle);
    } else {
      return (bubbledTo < index) ? new MoveDesc<E>(toTrickle, elementData(index)) : null;
    }
  }

  // Returned from removeAt() to iterator.remove()
  static class MoveDesc<E> {
    final E toTrickle;
    final E replaced;

    MoveDesc(E toTrickle, E replaced) {
      this.toTrickle = toTrickle;
      this.replaced = replaced;
    }
  }

  
Removes and returns the value at index. 
/** Removes and returns the value at {@code index}. */
  private E removeAndGet(int index) {
    E value = elementData(index);
    removeAt(index);
    return value;
  }

  private Heap heapForIndex(int i) {
    return isEvenLevel(i) ? minHeap : maxHeap;
  }

  private static final int EVEN_POWERS_OF_TWO = 0x55555555;
  private static final int ODD_POWERS_OF_TWO = 0xaaaaaaaa;

  @VisibleForTesting
  static boolean isEvenLevel(int index) {
    int oneBased = ~~(index + 1); // for GWT
    checkState(oneBased > 0, "negative index");
    return (oneBased & EVEN_POWERS_OF_TWO) > (oneBased & ODD_POWERS_OF_TWO);
  }

  
Returns true if the MinMax heap structure holds. This is only used in testing. 
TODO(kevinb): move to the test class?

/**
   * Returns {@code true} if the MinMax heap structure holds. This is only used in testing.
   *
   * <p>TODO(kevinb): move to the test class?
   */
  @VisibleForTesting
  boolean isIntact() {
    for (int i = 1; i < size; i++) {
      if (!heapForIndex(i).verifyIndex(i)) {
        return false;
      }
    }
    return true;
  }

  
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).

/**
   * 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).
   */
  @WeakOuter
  private class Heap {
    final Ordering<E> ordering;
    @MonotonicNonNull @Weak Heap otherHeap;

    Heap(Ordering<E> ordering) {
      this.ordering = ordering;
    }

    int compareElements(int a, int b) {
      return ordering.compare(elementData(a), elementData(b));
    }

    
Tries to move 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 removeAt. 
/**
     * Tries to move {@code toTrickle} from a min to a max level and bubble up there. If it moved
     * before {@code removeIndex} this method returns a pair as described in {@link #removeAt}.
     */
    MoveDesc<E> tryCrossOverAndBubbleUp(int removeIndex, int vacated, E toTrickle) {
      int crossOver = crossOver(vacated, toTrickle);
      if (crossOver == vacated) {
        return null;
      }
      // Successfully crossed over from min to max.
      // Bubble up max levels.
      E parent;
      // If toTrickle is moved up to a parent of removeIndex, the parent is
      // placed in removeIndex position. We must return that to the iterator so
      // that it knows to skip it.
      if (crossOver < removeIndex) {
        // We crossed over to the parent level in crossOver, so the parent
        // has already been moved.
        parent = elementData(removeIndex);
      } else {
        parent = elementData(getParentIndex(removeIndex));
      }
      // bubble it up the opposite heap
      if (otherHeap.bubbleUpAlternatingLevels(crossOver, toTrickle) < removeIndex) {
        return new MoveDesc<E>(toTrickle, parent);
      } else {
        return null;
      }
    }

    
Bubbles a value from index up the appropriate heap if required. 
/** Bubbles a value from {@code index} up the appropriate heap if required. */
    void bubbleUp(int index, E x) {
      int crossOver = crossOverUp(index, x);

      Heap heap;
      if (crossOver == index) {
        heap = this;
      } else {
        index = crossOver;
        heap = otherHeap;
      }
      heap.bubbleUpAlternatingLevels(index, x);
    }

    
Bubbles a value from index up the levels of this heap, and returns the index the element ended up at. 
/**
     * Bubbles a value from {@code index} up the levels of this heap, and returns the index the
     * element ended up at.
     */
    @CanIgnoreReturnValue
    int bubbleUpAlternatingLevels(int index, E x) {
      while (index > 2) {
        int grandParentIndex = getGrandparentIndex(index);
        E e = elementData(grandParentIndex);
        if (ordering.compare(e, x) <= 0) {
          break;
        }
        queue[index] = e;
        index = grandParentIndex;
      }
      queue[index] = x;
      return index;
    }

    
Returns the index of minimum value between index and index + len, or 
-1 if index is greater than size. 
/**
     * Returns the index of minimum value between {@code index} and {@code index + len}, or {@code
     * -1} if {@code index} is greater than {@code size}.
     */
    int findMin(int index, int len) {
      if (index >= size) {
        return -1;
      }
      checkState(index > 0);
      int limit = Math.min(index, size - len) + len;
      int minIndex = index;
      for (int i = index + 1; i < limit; i++) {
        if (compareElements(i, minIndex) < 0) {
          minIndex = i;
        }
      }
      return minIndex;
    }

    
Returns the minimum child or -1 if no child exists. 
/** Returns the minimum child or {@code -1} if no child exists. */
    int findMinChild(int index) {
      return findMin(getLeftChildIndex(index), 2);
    }

    
Returns the minimum grand child or -1 if no grand child exists. 
/** Returns the minimum grand child or -1 if no grand child exists. */
    int findMinGrandChild(int index) {
      int leftChildIndex = getLeftChildIndex(index);
      if (leftChildIndex < 0) {
        return -1;
      }
      return findMin(getLeftChildIndex(leftChildIndex), 4);
    }

    
Moves an element one level up from a min level to a max level (or vice versa). Returns the
new position of the element.

/**
     * Moves an element one level up from a min level to a max level (or vice versa). Returns the
     * new position of the element.
     */
    int crossOverUp(int index, E x) {
      if (index == 0) {
        queue[0] = x;
        return 0;
      }
      int parentIndex = getParentIndex(index);
      E parentElement = elementData(parentIndex);
      if (parentIndex != 0) {
        // This is a guard for the case of the childless uncle.
        // Since the end of the array is actually the middle of the heap,
        // a smaller childless uncle can become a child of x when we
        // bubble up alternate levels, violating the invariant.
        int grandparentIndex = getParentIndex(parentIndex);
        int uncleIndex = getRightChildIndex(grandparentIndex);
        if (uncleIndex != parentIndex && getLeftChildIndex(uncleIndex) >= size) {
          E uncleElement = elementData(uncleIndex);
          if (ordering.compare(uncleElement, parentElement) < 0) {
            parentIndex = uncleIndex;
            parentElement = uncleElement;
          }
        }
      }
      if (ordering.compare(parentElement, x) < 0) {
        queue[index] = parentElement;
        queue[parentIndex] = x;
        return parentIndex;
      }
      queue[index] = x;
      return index;
    }

    
Swap 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.

/**
     * Swap {@code actualLastElement} with the conceptually correct last element of the heap.
     * Returns the index that {@code actualLastElement} now resides in.
     *
     * <p>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 swapWithConceptuallyLastElement(E actualLastElement) {
      int parentIndex = getParentIndex(size);
      if (parentIndex != 0) {
        int grandparentIndex = getParentIndex(parentIndex);
        int uncleIndex = getRightChildIndex(grandparentIndex);
        if (uncleIndex != parentIndex && getLeftChildIndex(uncleIndex) >= size) {
          E uncleElement = elementData(uncleIndex);
          if (ordering.compare(uncleElement, actualLastElement) < 0) {
            queue[uncleIndex] = actualLastElement;
            queue[size] = uncleElement;
            return uncleIndex;
          }
        }
      }
      return size;
    }

    
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.

/**
     * Crosses an element over to the opposite heap by moving it one level down (or up if there are
     * no elements below it).
     *
     * <p>Returns the new position of the element.
     */
    int crossOver(int index, E x) {
      int minChildIndex = findMinChild(index);
      // TODO(kevinb): split the && into two if's and move crossOverUp so it's
      // only called when there's no child.
      if ((minChildIndex > 0) && (ordering.compare(elementData(minChildIndex), x) < 0)) {
        queue[index] = elementData(minChildIndex);
        queue[minChildIndex] = x;
        return minChildIndex;
      }
      return crossOverUp(index, x);
    }

    
Fills the hole at index 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)
/**
     * Fills the hole at {@code index} by moving in the least of its grandchildren to this position,
     * then recursively filling the new hole created.
     *
     * @return the position of the new hole (where the lowest grandchild moved from, that had no
     *     grandchild to replace it)
     */
    int fillHoleAt(int index) {
      int minGrandchildIndex;
      while ((minGrandchildIndex = findMinGrandChild(index)) > 0) {
        queue[index] = elementData(minGrandchildIndex);
        index = minGrandchildIndex;
      }
      return index;
    }

    private boolean verifyIndex(int i) {
      if ((getLeftChildIndex(i) < size) && (compareElements(i, getLeftChildIndex(i)) > 0)) {
        return false;
      }
      if ((getRightChildIndex(i) < size) && (compareElements(i, getRightChildIndex(i)) > 0)) {
        return false;
      }
      if ((i > 0) && (compareElements(i, getParentIndex(i)) > 0)) {
        return false;
      }
      if ((i > 2) && (compareElements(getGrandparentIndex(i), i) > 0)) {
        return false;
      }
      return true;
    }

    // These would be static if inner classes could have static members.

    private int getLeftChildIndex(int i) {
      return i * 2 + 1;
    }

    private int getRightChildIndex(int i) {
      return i * 2 + 2;
    }

    private int getParentIndex(int i) {
      return (i - 1) / 2;
    }

    private int getGrandparentIndex(int i) {
      return getParentIndex(getParentIndex(i)); // (i - 3) / 4
    }
  }

  
Iterates the elements of the queue in no particular order.

If the underlying queue is modified during iteration an exception will be thrown.

/**
   * Iterates the elements of the queue in no particular order.
   *
   * <p>If the underlying queue is modified during iteration an exception will be thrown.
   */
  private class QueueIterator implements Iterator<E> {
    private int cursor = -1;
    private int nextCursor = -1;
    private int expectedModCount = modCount;
    // The same element is not allowed in both forgetMeNot and skipMe, but duplicates are allowed in
    // either of them, up to the same multiplicity as the queue.
    @MonotonicNonNull private Queue<E> forgetMeNot;
    @MonotonicNonNull private List<E> skipMe;
    private @Nullable E lastFromForgetMeNot;
    private boolean canRemove;

    @Override
    public boolean hasNext() {
      checkModCount();
      nextNotInSkipMe(cursor + 1);
      return (nextCursor < size()) || ((forgetMeNot != null) && !forgetMeNot.isEmpty());
    }

    @Override
    public E next() {
      checkModCount();
      nextNotInSkipMe(cursor + 1);
      if (nextCursor < size()) {
        cursor = nextCursor;
        canRemove = true;
        return elementData(cursor);
      } else if (forgetMeNot != null) {
        cursor = size();
        lastFromForgetMeNot = forgetMeNot.poll();
        if (lastFromForgetMeNot != null) {
          canRemove = true;
          return lastFromForgetMeNot;
        }
      }
      throw new NoSuchElementException("iterator moved past last element in queue.");
    }

    @Override
    public void remove() {
      checkRemove(canRemove);
      checkModCount();
      canRemove = false;
      expectedModCount++;
      if (cursor < size()) {
        MoveDesc<E> moved = removeAt(cursor);
        if (moved != null) {
          if (forgetMeNot == null) {
            forgetMeNot = new ArrayDeque<E>();
            skipMe = new ArrayList<E>(3);
          }
          if (!foundAndRemovedExactReference(skipMe, moved.toTrickle)) {
            forgetMeNot.add(moved.toTrickle);
          }
          if (!foundAndRemovedExactReference(forgetMeNot, moved.replaced)) {
            skipMe.add(moved.replaced);
          }
        }
        cursor--;
        nextCursor--;
      } else { // we must have set lastFromForgetMeNot in next()
        checkState(removeExact(lastFromForgetMeNot));
        lastFromForgetMeNot = null;
      }
    }

    
Returns true if an exact reference (==) was found and removed from the supplied iterable. 
/** Returns true if an exact reference (==) was found and removed from the supplied iterable. */
    private boolean foundAndRemovedExactReference(Iterable<E> elements, E target) {
      for (Iterator<E> it = elements.iterator(); it.hasNext(); ) {
        E element = it.next();
        if (element == target) {
          it.remove();
          return true;
        }
      }
      return false;
    }

    
Removes only this exact instance, not others that are equals() 
/** Removes only this exact instance, not others that are equals() */
    private boolean removeExact(Object target) {
      for (int i = 0; i < size; i++) {
        if (queue[i] == target) {
          removeAt(i);
          return true;
        }
      }
      return false;
    }

    private void checkModCount() {
      if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
      }
    }

    
Advances nextCursor to the index of the first element after c that is not in 
skipMe and returns size() if there is no such element. 
/**
     * Advances nextCursor to the index of the first element after {@code c} that is not in {@code
     * skipMe} and returns {@code size()} if there is no such element.
     */
    private void nextNotInSkipMe(int c) {
      if (nextCursor < c) {
        if (skipMe != null) {
          while (c < size() && foundAndRemovedExactReference(skipMe, elementData(c))) {
            c++;
          }
        }
        nextCursor = c;
      }
    }
  }

  
Returns an iterator over the elements contained in this collection, in no particular
order.

The iterator is fail-fast: If the MinMaxPriorityQueue is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will generally throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. 
Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to
detect bugs.

Returns:an iterator over the elements contained in this collection
/**
   * Returns an iterator over the elements contained in this collection, <i>in no particular
   * order</i>.
   *
   * <p>The iterator is <i>fail-fast</i>: If the MinMaxPriorityQueue is modified at any time after
   * the iterator is created, in any way except through the iterator's own remove method, the
   * iterator will generally throw a {@link ConcurrentModificationException}. Thus, in the face of
   * concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary,
   * non-deterministic behavior at an undetermined time in the future.
   *
   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally
   * speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent
   * modification. Fail-fast iterators throw {@code ConcurrentModificationException} on a
   * best-effort basis. Therefore, it would be wrong to write a program that depended on this
   * exception for its correctness: <i>the fail-fast behavior of iterators should be used only to
   * detect bugs.</i>
   *
   * @return an iterator over the elements contained in this collection
   */
  @Override
  public Iterator<E> iterator() {
    return new QueueIterator();
  }

  @Override
  public void clear() {
    for (int i = 0; i < size; i++) {
      queue[i] = null;
    }
    size = 0;
  }

  @Override
  public Object[] toArray() {
    Object[] copyTo = new Object[size];
    System.arraycopy(queue, 0, copyTo, 0, size);
    return copyTo;
  }

  
Returns the comparator used to order the elements in this queue. Obeys the general contract of PriorityQueue.comparator, but returns Ordering.natural instead of null to indicate natural ordering. 
/**
   * Returns the comparator used to order the elements in this queue. Obeys the general contract of
   * {@link PriorityQueue#comparator}, but returns {@link Ordering#natural} instead of {@code null}
   * to indicate natural ordering.
   */
  public Comparator<? super E> comparator() {
    return minHeap.ordering;
  }

  @VisibleForTesting
  int capacity() {
    return queue.length;
  }

  // Size/capacity-related methods

  private static final int DEFAULT_CAPACITY = 11;

  @VisibleForTesting
  static int initialQueueSize(
      int configuredExpectedSize, int maximumSize, Iterable<?> initialContents) {
    // Start with what they said, if they said it, otherwise DEFAULT_CAPACITY
    int result =
        (configuredExpectedSize == Builder.UNSET_EXPECTED_SIZE)
            ? DEFAULT_CAPACITY
            : configuredExpectedSize;

    // Enlarge to contain initial contents
    if (initialContents instanceof Collection) {
      int initialSize = ((Collection<?>) initialContents).size();
      result = Math.max(result, initialSize);
    }

    // Now cap it at maxSize + 1
    return capAtMaximumSize(result, maximumSize);
  }

  private void growIfNeeded() {
    if (size > queue.length) {
      int newCapacity = calculateNewCapacity();
      Object[] newQueue = new Object[newCapacity];
      System.arraycopy(queue, 0, newQueue, 0, queue.length);
      queue = newQueue;
    }
  }

  
Returns ~2x the old capacity if small; ~1.5x otherwise. 
/** Returns ~2x the old capacity if small; ~1.5x otherwise. */
  private int calculateNewCapacity() {
    int oldCapacity = queue.length;
    int newCapacity =
        (oldCapacity < 64) ? (oldCapacity + 1) * 2 : IntMath.checkedMultiply(oldCapacity / 2, 3);
    return capAtMaximumSize(newCapacity, maximumSize);
  }

  
There's no reason for the queueSize to ever be more than maxSize + 1 
/** There's no reason for the queueSize to ever be more than maxSize + 1 */
  private static int capAtMaximumSize(int queueSize, int maximumSize) {
    return Math.min(queueSize - 1, maximumSize) + 1; // don't overflow
  }
}