下面列出了java.util.PriorityQueue#add ( ) 实例代码，或者点击链接到github查看源代码，也可以在右侧发表评论。
/**
* Get the top words under each topic given current Markov status.
*/
private ArrayList<PriorityQueue<Integer>> getTopWordsUnderEachTopicGivenCurrentMarkovStatus() {
ArrayList<PriorityQueue<Integer>> topWordIDList = new ArrayList<PriorityQueue<Integer>>();
int top_words = param.numberOfTopWordsUnderPriorTopicsForKnowledgeExtraction;
for (int t = 0; t < param.T; ++t) {
Comparator<Integer> comparator = new TopicalWordComparator(phi[t]);
PriorityQueue<Integer> pqueue = new PriorityQueue<Integer>(
top_words, comparator);
for (int w = 0; w < param.V; ++w) {
if (pqueue.size() < top_words) {
pqueue.add(w);
} else {
if (phi[t][w] > phi[t][pqueue.peek()]) {
pqueue.poll();
pqueue.add(w);
}
}
}
topWordIDList.add(pqueue);
}
return topWordIDList;
}
private static Queue<Double> findTopRelevanceScores(int n, HitGroup hits) {
PriorityQueue<Double> heap = new PriorityQueue<>(n);
for (var iterator = hits.unorderedDeepIterator(); iterator.hasNext(); ) {
Hit hit = iterator.next();
if (hit instanceof ErrorHit || hit.getRelevance() == null) {
continue;
}
double score = hit.getRelevance().getScore();
if (Double.isNaN(score)) {
continue;
}
if (heap.size() < n) {
heap.add(score);
} else if (score > heap.peek()) {
heap.remove();
heap.add(score);
}
}
return heap;
}
public Vertex selectVerticesToCoalesce() {
VertexComparator comparator = new VertexComparator(maxNumVarsInOneComp);
if (vertices.size() < 1) {
return null;
}
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>(vertices.size(),comparator);
for (Vertex vertex : vertices.values()) {
//System.out.println("adding vertex " + vertex.componentID);
vertexQueue.add(vertex);
}
// printVertexQueue(vertexQueue);
Vertex destVertex = vertexQueue.poll(); // vertexToMerge and its most connected neighbor will be coalesced into one component.
if (destVertex.getBestNetGain() < 0)
return null;
return destVertex;
}
public static int lessMoney(int[] arr) {
// Java 中小根堆可以采用优先级队列实现，如果实现大根堆重写比较器即可
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 将数组中元素全部塞入优先级队列
for (int i = 0; i < arr.length; i++) {
priorityQueue.add(arr[i]);
}
int sum = 0;
int cur = 0;
// 弹出两个最小的，计算其和并放入。
while (priorityQueue.size() > 1) {
cur = priorityQueue.poll() + priorityQueue.poll();
sum += cur;
priorityQueue.add(cur);
}
return sum;
}
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 static IdealState buildCustomIdealStateFor(String topicName,
int numTopicPartitions,
PriorityQueue<InstanceTopicPartitionHolder> instanceToNumServingTopicPartitionMap) {
final CustomModeISBuilder customModeIdealStateBuilder = new CustomModeISBuilder(topicName);
customModeIdealStateBuilder
.setStateModel(OnlineOfflineStateModel.name)
.setNumPartitions(numTopicPartitions).setNumReplica(1)
.setMaxPartitionsPerNode(numTopicPartitions);
for (int i = 0; i < numTopicPartitions; ++i) {
synchronized (instanceToNumServingTopicPartitionMap) {
InstanceTopicPartitionHolder liveInstance = instanceToNumServingTopicPartitionMap.poll();
customModeIdealStateBuilder.assignInstanceAndState(Integer.toString(i),
liveInstance.getInstanceName(), "ONLINE");
liveInstance.addTopicPartition(new TopicPartition(topicName, i));
instanceToNumServingTopicPartitionMap.add(liveInstance);
}
}
return customModeIdealStateBuilder.build();
}
public int[] getLeastNumbers(int[] arr, int k) {
int len = arr.length;
if (k == 0 || k > len) {
return new int[0];
}
// 应该使用大顶堆，传入 k 是为了防止扩容
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, (o1, o2) -> -o1 + o2);
for (int i = 0; i < k; i++) {
maxHeap.add(arr[i]);
}
for (int i = k; i < len; i++) {
Integer head = maxHeap.peek();
if (head > arr[i]) {
// 这里应该使用 replace ，但是 Java 不提供
maxHeap.poll();
maxHeap.add(arr[i]);
}
}
// 这样写一行太长，目前没找到更好的写法，意思就是直接读取最大堆里面的数组，而不去 poll
return Arrays.stream(maxHeap.toArray(new Integer[0])).mapToInt(Integer::valueOf).toArray();
}
private void solve() {
final PriorityQueue<PointToVisit> visitQueue = new PriorityQueue<>();
visitQueue.add(new PointToVisit(1.0, destination));
while (!visitQueue.isEmpty()) {
final PointToVisit visitPoint = visitQueue.poll();
visited[visitPoint.getLocation().getX()][visitPoint.getLocation().getY()] = true;
if (visitPoint.getLocation().equals(source)) {
return;
}
IndexedPoint lastPoint = sourceCells[visitPoint.getLocation().getX()][visitPoint.getLocation().getY()];
if (lastPoint == null) {
lastPoint = visitPoint.getLocation();
}
checkDirection(visitQueue, visitPoint.getScore(), lastPoint, visitPoint.getLocation(), 1, 0);
checkDirection(visitQueue, visitPoint.getScore(), lastPoint, visitPoint.getLocation(), -1, 0);
checkDirection(visitQueue, visitPoint.getScore(), lastPoint, visitPoint.getLocation(), 0, 1);
checkDirection(visitQueue, visitPoint.getScore(), lastPoint, visitPoint.getLocation(), 0, -1);
}
}
private PriorityQueue<SourceSegments> getSegmentsToMoveQueue(Map<String, Map<String, String>> idealStateMap,
List<String> srcHosts) {
PriorityQueue<SourceSegments> sourceSegments =
new PriorityQueue<>(idealStateMap.keySet().size(), new Comparator<SourceSegments>() {
@Override
public int compare(SourceSegments s1, SourceSegments s2) {
// arbitrary decision for equals case
return (s1.replicaCount > s2.replicaCount ? -1 : 1);
}
});
for (Map.Entry<String, Map<String, String>> segmentEntry : idealStateMap.entrySet()) {
SourceSegments srcSegment = new SourceSegments(segmentEntry.getKey(), 0);
for (Map.Entry<String, String> instanceEntry : segmentEntry.getValue().entrySet()) {
if (srcHosts.contains(instanceEntry.getKey())) {
++srcSegment.replicaCount;
}
}
if (srcSegment.replicaCount > 0) {
sourceSegments.add(srcSegment);
}
}
return sourceSegments;
}
/**
* clear removes all elements
*/
public void testClear() {
PriorityQueue q = populatedQueue(SIZE);
q.clear();
assertTrue(q.isEmpty());
assertEquals(0, q.size());
q.add(new Integer(1));
assertFalse(q.isEmpty());
q.clear();
assertTrue(q.isEmpty());
}
private void addEdges(OrderedWeightedGraph graph, int source,
PriorityQueue<DirectedEdge> directedEdges) {
Iterable<DirectedEdge> adj = graph.adj(source);
for (DirectedEdge edge : adj) {
directedEdges.add(edge);
}
}
private void calculateTopPredictions(final BoundingBox boundingBox, final PriorityQueue<Recognition> predictionQueue,
final List<String> labels) {
for (int i=0; i<boundingBox.getClasses().length; i++) {
ArgMax.Result argMax = new ArgMax(new SoftMax(boundingBox.getClasses()).getValue()).getResult();
double confidenceInClass = argMax.getMaxValue() * boundingBox.getConfidence();
if (confidenceInClass > THRESHOLD) {
predictionQueue.add(new Recognition(argMax.getIndex(), labels.get(argMax.getIndex()), (float) confidenceInClass,
new BoxPosition((float) (boundingBox.getX() - boundingBox.getWidth() / 2),
(float) (boundingBox.getY() - boundingBox.getHeight() / 2),
(float) boundingBox.getWidth(),
(float) boundingBox.getHeight())));
}
}
}
private List<Bucket> bucketLayers(final List<LayerData> sortedLayerList) {
final PriorityQueue<Bucket> bucketQueue = new PriorityQueue<>(numberOfBuckets);
int layerIndex = sortedLayerList.size() - 1;
for (int bucketIndex = 0; bucketIndex < numberOfBuckets; bucketIndex++) {
if (layerIndex >= 0) {
bucketQueue.add(new Bucket(sortedLayerList.get(layerIndex)));
layerIndex--;
} else {
break;
}
}
Bucket bucket;
for (; layerIndex >= 0; layerIndex--) {
bucket = bucketQueue.remove();
bucket.addLayer(sortedLayerList.get(layerIndex));
bucketQueue.add(bucket);
}
final List<Bucket> sortedBucketList = new ArrayList<>(numberOfBuckets);
sortedBucketList.addAll(bucketQueue.stream().collect(Collectors.toList()));
Collections.sort(sortedBucketList);
return sortedBucketList;
}
/**
* add(null) throws NPE
*/
public void testAddNull() {
PriorityQueue q = new PriorityQueue(1);
try {
q.add(null);
shouldThrow();
} catch (NullPointerException success) {}
}
private void calculateTopPredictions(final BoundingBox boundingBox, final PriorityQueue<Recognition> predictionQueue,
final Vector<String> labels) {
for (int i=0; i<boundingBox.getClasses().length; i++) {
ArgMax.Result argMax = new ArgMax(new SoftMax(boundingBox.getClasses()).getValue()).getResult();
double confidenceInClass = argMax.getMaxValue() * boundingBox.getConfidence();
if (confidenceInClass > THRESHOLD) {
predictionQueue.add(new Recognition(argMax.getIndex(), labels.get(argMax.getIndex()), (float) confidenceInClass,
new BoxPosition((float) (boundingBox.getX() - boundingBox.getWidth() / 2),
(float) (boundingBox.getY() - boundingBox.getHeight() / 2),
(float) boundingBox.getWidth(),
(float) boundingBox.getHeight())));
}
}
}
@Test
public void testPQReusability() {
List<Integer> SZs = genUniqueRandList(LOOPS);
PriorityQueue<Integer> PQ = new PriorityQueue<>();
BinaryHeapQuickRemovals<Integer> pq = new BinaryHeapQuickRemovals<>();
for (int sz : SZs) {
pq.clear();
PQ.clear();
List<Integer> nums = genRandList(sz);
for (int n : nums) {
pq.add(n);
PQ.add(n);
}
Collections.shuffle(nums);
for (int i = 0; i < sz / 2; i++) {
// Sometimes add a new number into the BinaryHeapQuickRemovals
if (0.25 < Math.random()) {
int randNum = (int) (Math.random() * 10000);
PQ.add(randNum);
pq.add(randNum);
}
int removeNum = nums.get(i);
assertTrue(pq.isMinHeap(0));
assertEquals(PQ.size(), pq.size());
assertEquals(PQ.peek(), pq.peek());
PQ.remove(removeNum);
pq.remove(removeNum);
assertEquals(PQ.peek(), pq.peek());
assertEquals(PQ.size(), pq.size());
assertTrue(pq.isMinHeap(0));
}
}
}
/**
* Updates the agenda with the result of all combinators that can be applied to leftChild and rightChild.
*/
private void updateAgenda(
final PriorityQueue<AgendaItem> agenda,
final int startOfSpan,
final int spanLength,
final SyntaxTreeNode leftChild,
final SyntaxTreeNode rightChild,
final int sentenceLength,
double outsideProbabilityUpperBound)
{
if (!seenRules.isSeen(leftChild.getCategory(), rightChild.getCategory())) {
return;
}
for (RuleProduction production : getRules(leftChild.getCategory(), rightChild.getCategory())) {
if ((leftChild.getRuleType() == RuleType.FC || leftChild.getRuleType() == RuleType.GFC) &&
(production.ruleType == RuleType.FA || production.ruleType == RuleType.FC || production.ruleType == RuleType.GFC)) {
// Eisner normal form constraint.
continue;
} else if ((rightChild.getRuleType() == RuleType.BX || leftChild.getRuleType() == RuleType.GBX) &&
(production.ruleType == RuleType.BA || production.ruleType == RuleType.BX || leftChild.getRuleType() == RuleType.GBX)) {
// Eisner normal form constraint.
continue;
} else if (leftChild.getRuleType() == RuleType.UNARY &&
production.ruleType == RuleType.FA && leftChild.getCategory().isForwardTypeRaised()) {
// Hockenmaier normal form constraint.
continue;
} else if (rightChild.getRuleType() == RuleType.UNARY &&
production.ruleType == RuleType.BA && rightChild.getCategory().isBackwardTypeRaised()) {
// Hockenmaier normal form constraint.
continue;
}else if (spanLength == sentenceLength && !possibleRootCategories.contains(production.category)) {
// Enforce that the root node must have one of a pre-specified list of categories.
continue ;
} else {
agenda.add(new AgendaItem(
nodeFactory.makeBinary(production.category, leftChild, rightChild, production.ruleType, production.headIsLeft),
outsideProbabilityUpperBound, startOfSpan, spanLength));
}
}
}
private boolean rebalanceBySwappingLoadOut(Broker broker,
ClusterModel clusterModel,
Set<Goal> optimizedGoals,
OptimizationOptions optimizationOptions,
boolean moveImmigrantsOnly) {
long swapStartTimeMs = System.currentTimeMillis();
if (!broker.isAlive() || optimizationOptions.excludedBrokersForReplicaMove().contains(broker.id())) {
// If the source broker is (1) dead, or (2) excluded for replica move, then swap operation is not possible.
return true;
}
Set<String> excludedTopics = optimizationOptions.excludedTopics();
// Get the replicas to swap.
String sourceReplicaSortName = sortedCandidateReplicas(broker,
excludedTopics,
0.0,
false,
false,
resource() == Resource.NW_OUT,
moveImmigrantsOnly);
SortedSet<Replica> sourceReplicas = broker.trackedSortedReplicas(sourceReplicaSortName).sortedReplicas(false);
if (sourceReplicas.isEmpty()) {
// Source broker has no filtered replica to swap.
broker.untrackSortedReplicas(sourceReplicaSortName);
return true;
}
// If this broker is excluded for leadership, then it can swapped with only followers.
double maxSourceReplicaLoad = getMaxReplicaLoad(sourceReplicas);
boolean swapWithFollowersOnly = optimizationOptions.excludedBrokersForLeadership().contains(broker.id());
PriorityQueue<Broker> candidateBrokerPQ = new PriorityQueue<>(_brokerComparator);
String candidateReplicaSortName = null;
for (Broker candidate : clusterModel.aliveBrokersUnderThreshold(resource(), _balanceUpperThreshold)
.stream().filter(b -> !b.replicas().isEmpty()).collect(Collectors.toSet())) {
// Get candidate replicas on candidate broker to try swapping with -- sorted in the order of trial (ascending load).
candidateReplicaSortName = sortedCandidateReplicas(candidate,
excludedTopics,
maxSourceReplicaLoad,
true,
swapWithFollowersOnly,
false,
moveImmigrantsOnly);
candidateBrokerPQ.add(candidate);
}
while (!candidateBrokerPQ.isEmpty()) {
if (remainingPerBrokerSwapTimeMs(swapStartTimeMs) <= 0) {
LOG.debug("Swap load out timeout for broker {}.", broker.id());
break;
}
Broker cb = candidateBrokerPQ.poll();
Replica swappedInReplica = null;
for (Replica sourceReplica : sourceReplicas) {
// Try swapping the source with the candidate replicas. Get the swapped in replica if successful, null otherwise.
Replica swappedIn = maybeApplySwapAction(clusterModel,
sourceReplica,
cb.trackedSortedReplicas(candidateReplicaSortName).sortedReplicas(false),
optimizedGoals,
optimizationOptions);
if (swappedIn != null) {
if (isLoadUnderBalanceUpperLimit(broker)) {
// Successfully balanced this broker by swapping in.
clusterModel.clearSortedReplicas();
return false;
}
// Add swapped in/out replica for updating the list of replicas in source broker.
swappedInReplica = swappedIn;
break;
} else if (remainingPerBrokerSwapTimeMs(swapStartTimeMs) <= 0) {
LOG.debug("Swap load out timeout for source replica {}.", sourceReplica);
clusterModel.clearSortedReplicas();
return true;
}
}
if (swappedInReplica != null) {
sourceReplicas = broker.trackedSortedReplicas(sourceReplicaSortName).sortedReplicas(false);
// The broker is still considered as an eligible candidate replica, because the swap was successful -- i.e. there
// might be other potential candidate replicas on it to swap with.
candidateBrokerPQ.add(cb);
}
}
clusterModel.clearSortedReplicas();
return true;
}
@Override
public List<Recognition> recognizeImage(final Bitmap bitmap) {
// Log this method so that it can be analyzed with systrace.
TraceCompat.beginSection("recognizeImage");
TraceCompat.beginSection("preprocessBitmap");
// Preprocess the image data from 0-255 int to normalized float based
// on the provided parameters.
bitmap.getPixels(intValues, 0, bitmap.getWidth(), 0, 0, bitmap.getWidth(), bitmap.getHeight());
for (int i = 0; i < intValues.length; ++i) {
final int val = intValues[i];
floatValues[i * 3 + 0] = (((val >> 16) & 0xFF) - imageMean) / imageStd;
floatValues[i * 3 + 1] = (((val >> 8) & 0xFF) - imageMean) / imageStd;
floatValues[i * 3 + 2] = ((val & 0xFF) - imageMean) / imageStd;
}
TraceCompat.endSection();
// Copy the input data into TensorFlow.
TraceCompat.beginSection("feed");
inferenceInterface.feed(
inputName, floatValues, new long[]{1, inputSize, inputSize, 3});
TraceCompat.endSection();
// Run the inference call.
TraceCompat.beginSection("run");
inferenceInterface.run(outputNames, runStats);
TraceCompat.endSection();
// Copy the output Tensor back into the output array.
TraceCompat.beginSection("fetch");
inferenceInterface.fetch(outputName, outputs);
TraceCompat.endSection();
// Find the best classifications.
PriorityQueue<Recognition> pq =
new PriorityQueue<Recognition>(
3,
new Comparator<Recognition>() {
@Override
public int compare(Recognition lhs, 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 < outputs.length; ++i) {
if (outputs[i] > THRESHOLD) {
pq.add(
new Recognition(
"" + i, labels.size() > i ? labels.get(i) : "unknown", outputs[i], null));
}
}
final ArrayList<Recognition> recognitions = new ArrayList<Recognition>();
int recognitionsSize = Math.min(pq.size(), MAX_RESULTS);
for (int i = 0; i < recognitionsSize; ++i) {
recognitions.add(pq.poll());
}
TraceCompat.endSection(); // "recognizeImage"
return recognitions;
}
@Test
public void testRandomInsertionsAndRemovals() {
for (int n = 1; n < 500; n++) {
List<Integer> indexes = genUniqueRandList(n);
MinIndexedBinaryHeap<Integer> pq1 = new MinIndexedBinaryHeap<Integer>(n);
PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>(n);
List<Integer> indexesToRemove = new ArrayList<>();
final double p = Math.random();
for (int i = 0; i < n; i++) {
int ii = indexes.get(i);
pq1.insert(ii, ii);
pq2.add(ii);
indexesToRemove.add(ii);
assertThat(pq1.isMinHeap()).isTrue();
if (Math.random() < p) {
int itemsToRemove = (int) (Math.random() * 10);
while (itemsToRemove-- > 0 && indexesToRemove.size() > 0) {
int iii = (int) (Math.random() * indexesToRemove.size());
int indexToRemove = indexesToRemove.get(iii);
boolean contains1 = pq1.contains(indexToRemove);
boolean contains2 = pq2.contains(indexToRemove);
assertThat(contains1).isEqualTo(contains2);
assertThat(pq1.isMinHeap()).isTrue();
if (contains2) {
pq1.delete(indexToRemove);
pq2.remove(indexToRemove);
indexesToRemove.remove(iii);
}
if (!pq2.isEmpty()) assertThat(pq1.peekMinValue()).isEqualTo(pq2.peek());
}
}
for (int index : indexesToRemove) {
assertThat(pq2.contains(index)).isTrue(); // Sanity check.
assertThat(pq1.contains(index)).isTrue();
}
assertThat(pq1.size()).isEqualTo(pq2.size());
assertThat(pq1.isEmpty()).isEqualTo(pq2.isEmpty());
if (!pq2.isEmpty()) assertThat(pq1.peekMinValue()).isEqualTo(pq2.peek());
}
}
}