下面列出了java.util.PriorityQueue#poll ( ) 实例代码，或者点击链接到github查看源代码，也可以在右侧发表评论。
/**
* Heap.
* Suppose len(nums1) = m, len(nums2) = n, there can be m * n pairs.
* All integers in nums1 should start from the first integer in nums2.
* So add the first k pairs to a priority queue pq based on the sum.
* Then poll from pq and add it to result.
* Move the index in nums2 for the integer in nums1 one step further if possible.
* Then add the new pair to pq.
* Stop when we have k pairs.
* https://discuss.leetcode.com/topic/50885/simple-java-o-klogk-solution-with-explanation/2
*/
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] + a[1] - b[0] - b[1]);
List<int[]> res = new ArrayList<>();
if (nums1.length == 0 || nums2.length == 0 || k == 0) {
return res;
}
for (int i = 0; i < nums1.length && i < k; i++) {
pq.offer(new int[]{nums1[i], nums2[0], 0});
}
while (k-- > 0 && !pq.isEmpty()) {
int[] cur = pq.poll();
res.add(new int[]{cur[0], cur[1]});
if (cur[2] == nums2.length - 1) {
continue;
}
pq.offer(new int[]{cur[0], nums2[cur[2] + 1], cur[2] + 1});
}
return res;
}
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> mapCount = new HashMap<>();
//统计出现频率
for (int n : nums) {
mapCount.put(n, mapCount.getOrDefault(n, 0) + 1);
}
//创建大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> mapCount.get(a) - mapCount.get(b));
for (int key : mapCount.keySet()) {
maxHeap.add(key);
if (maxHeap.size() > k) {
maxHeap.poll();
}
}
int[] ans = new int[k];
int t = k - 1;
while (!maxHeap.isEmpty()) {
ans[t--] = maxHeap.poll();
}
return ans;
}
/**
*
* @param vector
* @param n
* @return
*/
public List<SpaceResult> findSimilar(float[] vector, int n) {
PriorityQueue<SpaceResult> queue = new PriorityQueue<>();
Iterator<String> iterator = memory.keySet().iterator();
while (iterator.hasNext()) {
String key = iterator.next();
float[] v2 = memory.get(key);
float score = VectorUtils.scalarProduct(vector, v2);
if (queue.size() < n) {
queue.offer(new SpaceResult(key, score));
} else {
queue.poll();
queue.offer(new SpaceResult(key, score));
}
}
queue.poll();
List<SpaceResult> list = new ArrayList<>(queue);
Collections.sort(list);
return list;
}
/**
*
* @param word
* @param n
* @return
*/
public List<SpaceResult> findSimilar(String word, int n) {
float[] v1 = vectors.get(word);
if (v1 == null) {
Logger.getLogger(LuceneVectorStore.class.getName()).log(Level.WARNING, "No vector for term: {0}", word);
return new ArrayList<>();
}
PriorityQueue<SpaceResult> queue = new PriorityQueue<>();
Iterator<String> iterator = vectors.keySet().iterator();
while (iterator.hasNext()) {
String key = iterator.next();
float[] v2 = vectors.get(key);
float score = VectorUtils.scalarProduct(v1, v2);
if (queue.size() < n) {
queue.offer(new SpaceResult(key, score));
} else {
queue.poll();
queue.offer(new SpaceResult(key, score));
}
}
queue.poll();
List<SpaceResult> list = new ArrayList<>(queue);
Collections.sort(list);
return list;
}
private void onNextRow(PriorityQueue<Object[]> pq, Row row) {
for (CollectExpression<Row, ?> expression : expressions) {
expression.setNextRow(row);
}
Object[] rowCells = new Object[inputs.size()];
int i = 0;
for (Input<?> input : inputs) {
rowCells[i] = input.value();
i++;
}
rowAccounting.accountForAndMaybeBreak(rowCells);
if (pq.size() == maxNumberOfRowsInQueue) {
Object[] highestElementInOrder = pq.peek();
if (highestElementInOrder == null || comparator.compare(rowCells, highestElementInOrder) < 0) {
pq.poll();
pq.add(rowCells);
}
} else {
pq.add(rowCells);
}
}
private List<Recognition> getRecognition(final PriorityQueue<Recognition> priorityQueue) {
List<Recognition> recognitions = new ArrayList();
if (priorityQueue.size() > 0) {
// Best recognition
Recognition bestRecognition = priorityQueue.poll();
recognitions.add(bestRecognition);
for (int i = 0; i < Math.min(priorityQueue.size(), MAX_RESULTS); ++i) {
Recognition recognition = priorityQueue.poll();
boolean overlaps = false;
for (Recognition previousRecognition : recognitions) {
overlaps = overlaps || (getIntersectionProportion(previousRecognition.getLocation(),
recognition.getLocation()) > OVERLAP_THRESHOLD);
}
if (!overlaps) {
recognitions.add(recognition);
}
}
}
return recognitions;
}
private static int mst(int n, PriorityQueue<Edge> edges) {
int [] parent=new int [n];
for (int i=0;i<n;i++) parent[i]=i;
int dist=0;
while (!edges.isEmpty()) {
Edge e=edges.poll();
int px=getParent(parent, e.x);
int py=getParent(parent, e.y);
if (px!=py) {
if (px>py) parent[px]=py;
else parent[py]=px;
dist=Math.max(dist, e.dist);
}
}
for (int i=0;i<n;i++) if (getParent(parent,0)!=getParent(parent,i)) {
dist=-1;
break;
}
return dist;
}
/**
* Heap. Priority queue. O(nlogk) Time, O(k) Space.
* Create a min heap as a window.
* For each number in the array, add it to the heap.
* If heap size > k, poll from the heap.
* Return the top of the heap at the end.
*/
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int n : nums) {
pq.offer(n);
if (pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
public int kthSmallest(int[][] matrix, int k) {
PriorityQueue<Tuple> queue = new PriorityQueue<>();
for (int j = 0; j < matrix.length; j++) queue.offer(new Tuple(0, j, matrix[0][j]));
while (--k != 0) {
Tuple entry = queue.poll();
if (entry.x < matrix.length - 1) {
queue.offer(new Tuple(entry.x + 1, entry.y, matrix[entry.x + 1][entry.y]));
}
}
return queue.poll().val;
}
/**
* Finds the next broker in the broker queue for migrating a replica
* @param brokerQueue a queue of brokers ordered by utilization
* @param unusableBrokers the brokers that should not be used for reassignment
* @param replicaBrokers the ids of the brokers that are already used for this replica
* @param reassignmentMap the replica -> target broker mapping for the next reassignment
* @param oosBrokerId the broker id of the current OutOfSync replica
* @param tp the TopicPartition of the current replica
* @param inBoundReq inbound traffic that needs to be reserved
* @param outBoundReq outbound traffic that needs to be reserved
* @param preferredBroker the preferred leader of the current TopicPartition
* @return true if we successfully assigned a target broker for migration of this replica false otherwise
*/
protected boolean findNextBrokerForOosReplica(
PriorityQueue<KafkaBroker> brokerQueue,
Collection<KafkaBroker> unusableBrokers,
Collection<Integer> replicaBrokers,
Map<Integer, KafkaBroker> reassignmentMap,
Integer oosBrokerId,
TopicPartition tp,
Double inBoundReq,
Double outBoundReq,
Integer preferredBroker
){
boolean success;
KafkaBroker leastUsedBroker = brokerQueue.poll();
while (leastUsedBroker != null && replicaBrokers.contains(leastUsedBroker.getId())) {
unusableBrokers.add(leastUsedBroker);
leastUsedBroker = brokerQueue.poll();
}
if (leastUsedBroker == null) {
LOG.error("Failed to find a usable broker for fixing {}:{}", tp, oosBrokerId);
success = false;
} else {
LOG.info("LeastUsedBroker for replacing {} : {}", oosBrokerId, leastUsedBroker.getId());
success = preferredBroker == oosBrokerId ?
leastUsedBroker.reserveBandwidth(tp, inBoundReq, outBoundReq) :
leastUsedBroker.reserveBandwidth(tp, inBoundReq, 0);
if (success) {
reassignmentMap.put(oosBrokerId, leastUsedBroker);
// the broker should not be used again for this topic partition.
unusableBrokers.add(leastUsedBroker);
} else {
LOG.error("Failed to allocate resource to replace {}:{}", tp, oosBrokerId);
}
}
return success;
}
@Override
public DataBag exec(Tuple input) throws IOException
{
DataBag outputBag = bagFactory.newDefaultBag();
PriorityQueue<pair> pq = load_bags(input);
if(pq.size() != input.size())
return outputBag; // one or more input bags were empty
Tuple last_data = null;
while (true) {
if (pq.peek().data.compareTo(last_data) != 0 && all_equal(pq)) {
last_data = pq.peek().data;
outputBag.add(last_data);
}
pair p = pq.poll();
if (!p.it.hasNext())
break;
Tuple nextData = p.it.next();
// algorithm assumes data is in order
if (p.data.compareTo(nextData) > 0)
{
throw new RuntimeException("Out of order!");
}
p.data = nextData;
pq.offer(p);
}
return outputBag;
}
public static FloatElement[] topNSort(final float[] vec, final int topN,
final Set<Integer> exclusions) {
final Comparator<FloatElement> valAscending = new FloatElement.ValueComparator(
false);
final Comparator<FloatElement> valDescending = new FloatElement.ValueComparator(
true);
PriorityQueue<FloatElement> heap = new PriorityQueue<FloatElement>(topN,
valAscending);
for (int i = 0; i < vec.length; i++) {
if (exclusions != null && exclusions.contains(i) == true) {
continue;
}
float val = vec[i];
if (heap.size() < topN) {
heap.add(new FloatElement(i, val));
} else {
if (heap.peek().value < val) {
heap.poll();
heap.add(new FloatElement(i, val));
}
}
}
FloatElement[] heapArray = new FloatElement[heap.size()];
heap.toArray(heapArray);
Arrays.sort(heapArray, valDescending);
return heapArray;
}
private Bucket pqToIterable(PriorityQueue<Object[]> pq) {
if (offset > pq.size()) {
return new ArrayBucket(new Object[0][0], numOutputs);
}
int resultSize = Math.max(Math.min(maxNumberOfRowsInQueue - offset, pq.size() - offset), 0);
Object[][] rows = new Object[resultSize][];
for (int i = resultSize - 1; i >= 0; i--) {
rows[i] = pq.poll();
}
return new ArrayBucket(rows, numOutputs);
}
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 最小堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k + 1, (a, b) -> (a - b));
for (int i = 0; i < k; i++) {
priorityQueue.add(nums[i]);
}
for (int i = k; i < len; i++) {
priorityQueue.add(nums[i]);
priorityQueue.poll();
}
return priorityQueue.peek();
}
public static void main (String [] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s;
while ((s=br.readLine())!=null) {
int N=Integer.parseInt(s);
TreeMap<Integer, Integer> map=new TreeMap<>();
StringTokenizer st=new StringTokenizer(br.readLine());
for (int n=0;n<N;n++) {
int v=Integer.parseInt(st.nextToken());
map.put(v, map.getOrDefault(v, 0)+1);
}
int sum=Integer.parseInt(br.readLine());
PriorityQueue<Solution> q=new PriorityQueue<>();
ArrayList<Integer> list=new ArrayList<>();
list.addAll(map.keySet());
for (int i=0;i<list.size();i++) {
int p1=list.get(i);
int p2=sum-p1;
if ((p1==p2 && map.get(p1)>=2) || (p1!=p2 && map.containsKey(p2))) q.offer(new Solution(p1, p2));
}
Solution sol=q.poll();
System.out.printf("Peter should buy books whose prices are %d and %d.\n\n", sol.small, sol.large);
br.readLine();
}
}
/**
* Provide spelling corrections based on several parameters.
*
* @param term The term to suggest spelling corrections for
* @param numSug The maximum number of spelling corrections
* @param ir The index reader to fetch the candidate spelling corrections from
* @param docfreq The minimum document frequency a potential suggestion need to have in order to be included
* @param editDistance The maximum edit distance candidates are allowed to have
* @param accuracy The minimum accuracy a suggested spelling correction needs to have in order to be included
* @param spare a chars scratch
* @return a collection of spelling corrections sorted by <code>ScoreTerm</code>'s natural order.
* @throws IOException If I/O related errors occur
*/
protected Collection<ScoreTerm> suggestSimilar(Term term, int numSug, IndexReader ir, int docfreq, int editDistance,
float accuracy, final CharsRefBuilder spare) throws IOException {
Terms terms = MultiTerms.getTerms(ir, term.field());
if (terms == null) {
return Collections.emptyList();
}
FuzzyTermsEnum e = new FuzzyTermsEnum(terms, term, editDistance, Math.max(minPrefix, editDistance - 1), true);
final PriorityQueue<ScoreTerm> stQueue = new PriorityQueue<>();
BytesRef queryTerm = new BytesRef(term.text());
BytesRef candidateTerm;
ScoreTerm st = new ScoreTerm();
while ((candidateTerm = e.next()) != null) {
// For FuzzyQuery, boost is the score:
float score = e.getBoost();
// ignore uncompetitive hits
if (stQueue.size() >= numSug && score <= stQueue.peek().boost) {
continue;
}
// ignore exact match of the same term
if (queryTerm.bytesEquals(candidateTerm)) {
continue;
}
int df = e.docFreq();
// check docFreq if required
if (df <= docfreq) {
continue;
}
final String termAsString;
if (distance == INTERNAL_LEVENSHTEIN) {
// delay creating strings until the end
termAsString = null;
} else {
spare.copyUTF8Bytes(candidateTerm);
termAsString = spare.toString();
score = distance.getDistance(term.text(), termAsString);
}
if (score < accuracy) {
continue;
}
// add new entry in PQ
st.term = BytesRef.deepCopyOf(candidateTerm);
st.boost = score;
st.docfreq = df;
st.termAsString = termAsString;
st.score = score;
stQueue.offer(st);
// possibly drop entries from queue
st = (stQueue.size() > numSug) ? stQueue.poll() : new ScoreTerm();
e.setMaxNonCompetitiveBoost((stQueue.size() >= numSug) ? stQueue.peek().boost : Float.NEGATIVE_INFINITY);
}
return stQueue;
}
private boolean rebalanceByMovingLoadIn(Broker broker,
ClusterModel clusterModel,
Set<Goal> optimizedGoals,
ActionType actionType,
OptimizationOptions optimizationOptions,
boolean moveImmigrantsOnly) {
if (!clusterModel.newBrokers().isEmpty() && !broker.isNew()) {
// We have new brokers and the current broker is not a new broker.
return true;
}
Set<String> excludedTopics = optimizationOptions.excludedTopics();
// If this broker is excluded for leadership, then it can move in only followers.
boolean moveFollowersOnly = optimizationOptions.excludedBrokersForLeadership().contains(broker.id());
PriorityQueue<Broker> candidateBrokerPQ = new PriorityQueue<>(_brokerComparator.reversed());
double clusterUtilization = clusterModel.load().expectedUtilizationFor(resource()) / clusterModel.capacityFor(resource());
String replicaSortName = null;
for (Broker candidate : clusterModel.aliveBrokers()) {
// Get candidate replicas on candidate broker to try moving load from -- sorted in the order of trial (descending load).
if (utilizationPercentage(candidate, resource()) > clusterUtilization) {
replicaSortName = sortedCandidateReplicas(candidate,
excludedTopics,
0.0,
false,
moveFollowersOnly,
resource() == Resource.NW_OUT,
moveImmigrantsOnly);
candidateBrokerPQ.add(candidate);
}
}
// Stop when all the replicas are leaders for leader movement or there is no replicas can be moved in anymore
// for replica movement.
while (!candidateBrokerPQ.isEmpty() && (actionType == INTER_BROKER_REPLICA_MOVEMENT ||
(actionType == LEADERSHIP_MOVEMENT && broker.leaderReplicas().size() != broker.replicas().size()))) {
Broker cb = candidateBrokerPQ.poll();
SortedSet<Replica> candidateReplicasToReceive = cb.trackedSortedReplicas(replicaSortName).sortedReplicas(true);
for (Iterator<Replica> iterator = candidateReplicasToReceive.iterator(); iterator.hasNext(); ) {
Replica replica = iterator.next();
Broker b = maybeApplyBalancingAction(clusterModel, replica, Collections.singletonList(broker), actionType,
optimizedGoals, optimizationOptions);
// Only need to check status if the action is taken. This will also handle the case that the source broker
// has nothing to move in. In that case we will never reenqueue that source broker.
if (b != null) {
if (isLoadAboveBalanceLowerLimit(broker)) {
clusterModel.untrackSortedReplicas(replicaSortName);
return false;
}
// Remove the replica from its source broker if it was a replica movement.
if (actionType == INTER_BROKER_REPLICA_MOVEMENT) {
iterator.remove();
}
// If the source broker has a lower utilization than the next broker in the eligible broker in the queue,
// we reenqueue the source broker and switch to the next broker.
if (!candidateBrokerPQ.isEmpty()
&& utilizationPercentage(cb, resource()) < utilizationPercentage(candidateBrokerPQ.peek(), resource())) {
candidateBrokerPQ.add(cb);
break;
}
}
}
}
clusterModel.untrackSortedReplicas(replicaSortName);
return true;
}
public static void main (String [] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int T=Integer.parseInt(br.readLine());
for (int t=0;t<T;t++) {
StringTokenizer st=new StringTokenizer(br.readLine());
int [] maxFilled= {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
int D=Integer.parseInt(st.nextToken());
int [] maxPour=new int [D+1];
Arrays.fill(maxPour, Integer.MAX_VALUE);
HashMap<String, Integer> stateDist=new HashMap<>();
Edge start=new Edge(0,0,maxFilled[2],0);
stateDist.put(start.toString(), 0);
PriorityQueue<Edge> q=new PriorityQueue<>();
q.offer(start);
while (!q.isEmpty()) {
Edge e=q.poll();
for (int i=0;i<e.filled.length;i++) if (e.filled[i]<maxPour.length) maxPour[e.filled[i]]=Math.min(maxPour[e.filled[i]], e.dist);
for (int jugS=0;jugS<e.filled.length;jugS++) if (e.filled[jugS]>0) for (int jugD=0;jugD<e.filled.length;jugD++) if (e.filled[jugD]<maxFilled[jugD] && jugS!=jugD) {
int pour=Math.min(e.filled[jugS], maxFilled[jugD]-e.filled[jugD]);
Edge next=new Edge(e);
next.filled[jugS]-=pour;
next.filled[jugD]+=pour;
next.dist+=pour;
String nextKey=next.toString();
if (next.dist < stateDist.getOrDefault(nextKey, Integer.MAX_VALUE)) {
stateDist.put(nextKey, next.dist);
q.offer(next);
}
}
}
int ans=-1, ansPour=-1;
for (int i=D;i>=0;i--) if (maxPour[i]!=Integer.MAX_VALUE) {
ans=i;
ansPour=maxPour[i];
break;
}
System.out.printf("%d %d\n",ansPour,ans);
}
}
/**
* <p>
* We assume here that the passed-in inner LinkedHashMaps are already sorted
* in order of "Best Possible Correction".
* </p>
*/
public PossibilityIterator(
Map<Token,LinkedHashMap<String,Integer>> suggestions,
int maximumRequiredSuggestions, int maxEvaluations, boolean overlap) {
this.suggestionsMayOverlap = overlap;
for (Map.Entry<Token,LinkedHashMap<String,Integer>> entry : suggestions
.entrySet()) {
Token token = entry.getKey();
if (entry.getValue().size() == 0) {
continue;
}
List<SpellCheckCorrection> possibleCorrections = new ArrayList<>();
for (Map.Entry<String,Integer> entry1 : entry.getValue().entrySet()) {
SpellCheckCorrection correction = new SpellCheckCorrection();
correction.setOriginal(token);
correction.setCorrection(entry1.getKey());
correction.setNumberOfOccurences(entry1.getValue());
possibleCorrections.add(correction);
}
possibilityList.add(possibleCorrections);
}
int wrapSize = possibilityList.size();
if (wrapSize == 0) {
done = true;
} else {
correctionIndex = new int[wrapSize];
for (int i = 0; i < wrapSize; i++) {
int suggestSize = possibilityList.get(i).size();
if (suggestSize == 0) {
done = true;
break;
}
correctionIndex[i] = 0;
}
}
PriorityQueue<RankedSpellPossibility> rankedPossibilities = new PriorityQueue<>(
11, new RankComparator());
Set<RankedSpellPossibility> removeDuplicates = null;
if (suggestionsMayOverlap) {
removeDuplicates = new HashSet<>();
}
long numEvaluations = 0;
while (numEvaluations < maxEvaluations && internalHasNext()) {
RankedSpellPossibility rsp = internalNext();
numEvaluations++;
if (rankedPossibilities.size() >= maximumRequiredSuggestions
&& rsp.rank >= rankedPossibilities.peek().rank) {
continue;
}
if (!isSuggestionForReal(rsp)) {
continue;
}
if (removeDuplicates == null) {
rankedPossibilities.offer(rsp);
} else {
// Needs to be in token-offset order so that the match-and-replace
// option for collations can work.
Collections.sort(rsp.corrections, new StartOffsetComparator());
if (removeDuplicates.add(rsp)) {
rankedPossibilities.offer(rsp);
}
}
if (rankedPossibilities.size() > maximumRequiredSuggestions) {
RankedSpellPossibility removed = rankedPossibilities.poll();
if (removeDuplicates != null) {
removeDuplicates.remove(removed);
}
}
}
RankedSpellPossibility[] rpArr = new RankedSpellPossibility[rankedPossibilities
.size()];
for (int i = rankedPossibilities.size() - 1; i >= 0; i--) {
rpArr[i] = rankedPossibilities.remove();
}
rankedPossibilityIterator = Arrays.asList(rpArr).iterator();
}
public static void main (String [] args) throws Exception {
Scanner sc=new Scanner(System.in);
int testCaseCount=sc.nextInt();
for (int testCase=1;testCase<=testCaseCount;testCase++) {
int N=sc.nextInt();
int M=sc.nextInt();
int K=sc.nextInt();
boolean [] airport=new boolean [N+1];
for (int k=0;k<K;k++) airport[sc.nextInt()]=true;
int [][] adjMat=new int [N+1][N+1];
for (int i=0;i<adjMat.length;i++) Arrays.fill(adjMat[i], Integer.MAX_VALUE);
for (int m=0;m<M;m++) {
int a=sc.nextInt();
int b=sc.nextInt();
adjMat[a][b]=(airport[b]) ? 0 : 1;
adjMat[b][a]=(airport[a]) ? 0 : 1;
}
StringBuilder sb=new StringBuilder();
sb.append("Case ");
sb.append(testCase);
sb.append(":\n");
int Q=sc.nextInt();
for (int q=0;q<Q;q++) {
int x=sc.nextInt();
int y=sc.nextInt();
int [] minDist=new int [N+1];
Arrays.fill(minDist, Integer.MAX_VALUE);
if (x!=y) {
PriorityQueue<Tuple> queue=new PriorityQueue<>();
minDist[x]=airport[x] ? 0 : 1;
queue.offer(new Tuple(x,minDist[x]));
while (!queue.isEmpty()) {
Tuple t=queue.poll();
if (t.n==y) break;
if (t.d != minDist[t.n]) continue;
for (int i=1;i<=N;i++) if (adjMat[t.n][i]!=Integer.MAX_VALUE && t.d+adjMat[t.n][i]<minDist[i]) {
minDist[i]=t.d+adjMat[t.n][i];
queue.offer(new Tuple(i,minDist[i]));
}
}
} else minDist[x]=0;
sb.append(minDist[y]!=Integer.MAX_VALUE ? minDist[y] : -1);
sb.append('\n');
}
System.out.println(sb.toString());
}
}