下面列出了java.util.PriorityQueue#offer ( ) 实例代码,或者点击链接到github查看源代码,也可以在右侧发表评论。
public static void main (String [] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int testCase=1;
while (true) {
int n=Integer.parseInt(br.readLine());
if (n==0) break;
int [][] nodes=new int [n][2];
PriorityQueue<Edge> edges=new PriorityQueue<>();
for (int i=0;i<nodes.length;i++) {
StringTokenizer st=new StringTokenizer(br.readLine());
nodes[i][0]=Integer.parseInt(st.nextToken());
nodes[i][1]=Integer.parseInt(st.nextToken());
}
for (int i=0;i<nodes.length-1;i++) for (int i2=i+1;i2<nodes.length;i2++) {
double dist=Math.sqrt(Math.pow(nodes[i][0]-nodes[i2][0], 2)+Math.pow(nodes[i][1]-nodes[i2][1], 2));
edges.offer(new Edge(i, i2, dist));
}
System.out.printf("Scenario #%d\nFrog Distance = %.3f\n\n", testCase++, mst(n, edges));
br.readLine();
}
}
/**
* java.util.PriorityQueue#PriorityQueue(PriorityQueue<? * extends
*E>)
*/
public void test_ConstructorLjava_util_PriorityQueue() {
PriorityQueue<Integer> integerQueue = new PriorityQueue<Integer>();
int[] array = { 2, 45, 7, -12, 9 };
for (int i = 0; i < array.length; i++) {
integerQueue.offer(array[i]);
}
PriorityQueue<Object> objectQueue = new PriorityQueue<Object>(
integerQueue);
assertEquals(integerQueue.size(), objectQueue.size());
assertEquals(integerQueue.comparator(), objectQueue.comparator());
Arrays.sort(array);
for (int i = 0; i < array.length; i++) {
assertEquals(array[i], objectQueue.poll());
}
}
@Test
public void testInQueue() {
PriorityQueue<ExponentialBackoff> queue = new PriorityQueue<>();
ExponentialBackoff backoff1 = new ExponentialBackoff(params);
backoff.trackFailure();
backoff.trackFailure();
backoff1.trackFailure();
backoff1.trackFailure();
backoff1.trackFailure();
queue.offer(backoff);
queue.offer(backoff1);
assertEquals(queue.poll(), backoff); // The one with soonest retry time
assertEquals(queue.peek(), backoff1);
queue.offer(backoff);
assertEquals(queue.poll(), backoff); // Still the same one
}
/**
* O(nlogk)的算法,特别适合处理海量数据
* 基于堆或者红黑树
* @param array
* @param k
* @return
*/
public ArrayList<Integer> getLeastNumbers(int[] array, int k) {
if(array == null || array.length == 0 || k > array.length || k <= 0) {
return new ArrayList<>();
}
PriorityQueue<Integer> kLeastNumbers = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for (int i = 0; i < array.length; i++) {
if(kLeastNumbers.size() < k) {
kLeastNumbers.offer(array[i]);
} else {
if(kLeastNumbers.peek() > array[i]) {
kLeastNumbers.poll();
kLeastNumbers.offer(array[i]);
}
}
}
return new ArrayList<>(kLeastNumbers);
}
/**
* 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 static void djikstra(ArrayList<Edge> [] edgeList, int [] lowestCost, int src, int dest) {
lowestCost[src]=0;
PriorityQueue<Edge> queue=new PriorityQueue<>();
queue.add(new Edge(src,src,0));
while (!queue.isEmpty()) {
Edge e=queue.poll();
if (e.dest==dest) break;
else if (edgeList[e.dest]!=null) {
for (Edge ed : edgeList[e.dest]) {
if (lowestCost[ed.dest]>lowestCost[ed.src]+ed.cost) {
lowestCost[ed.dest]=lowestCost[ed.src]+ed.cost;
queue.offer(new Edge(ed.src,ed.dest,lowestCost[ed.dest]));
}
}
}
}
}
@Override
public void processElement(StreamRecord<IN> element) throws Exception {
String streamId = getStreamId(element.getValue());
StreamSchema<IN> schema = siddhiPlan.getInputStreamSchema(streamId);
if (isProcessingTime) {
processEvent(streamId, schema, element.getValue(), System.currentTimeMillis());
this.checkpointSiddhiRuntimeState();
} else {
PriorityQueue<StreamRecord<IN>> priorityQueue = getPriorityQueue();
// event time processing
// we have to buffer the elements until we receive the proper watermark
if (getExecutionConfig().isObjectReuseEnabled()) {
// copy the StreamRecord so that it cannot be changed
priorityQueue.offer(new StreamRecord<>(schema.getTypeSerializer().copy(element.getValue()), element.getTimestamp()));
} else {
priorityQueue.offer(element);
}
this.checkpointRecordQueueState();
}
}
/**
* Execute the provided {@link Runnable} after the next call to {@link
* #fireForWatermark(AppliedPTransform, Instant)} where the window is guaranteed to be expired.
*/
public void callOnWindowExpiration(
AppliedPTransform<?, ?, ?> step,
BoundedWindow window,
WindowingStrategy<?, ?> windowingStrategy,
Runnable runnable) {
WatermarkCallback callback =
WatermarkCallback.afterWindowExpiration(window, windowingStrategy, runnable);
PriorityQueue<WatermarkCallback> callbackQueue = callbacks.get(step);
if (callbackQueue == null) {
callbackQueue = new PriorityQueue<>(11, new CallbackOrdering());
if (callbacks.putIfAbsent(step, callbackQueue) != null) {
callbackQueue = callbacks.get(step);
}
}
synchronized (callbackQueue) {
callbackQueue.offer(callback);
}
}
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> result = new ArrayList<>();
if (nums1.length == 0 || nums2.length == 0) return result;
PriorityQueue<Tuple> queue = new PriorityQueue<>();
for (int i = 0; i < nums1.length; i++) {
queue.offer(new Tuple(i, 0, nums1[i] + nums2[0]));
}
while (k-- != 0 && queue.size() > 0) {
Tuple tuple = queue.poll();
if (tuple.y + 1 < nums2.length)
queue.offer(new Tuple(tuple.x, tuple.y + 1, nums1[tuple.x] + nums2[tuple.y + 1]));
result.add(new int[]{nums1[tuple.x], nums2[tuple.y]});
}
return result;
}
/**
* java.util.PriorityQueue#PriorityQueue(Collection)
*/
public void test_ConstructorLjava_util_Colleciton_from_priorityqueue() {
String[] array = { "AAAAA", "AA", "AAAA", "AAAAAAAA" };
PriorityQueue<String> queue = new PriorityQueue<String>(4,
new MockComparatorStringByLength());
for (int i = 0; i < array.length; i++) {
queue.offer(array[i]);
}
Collection<String> c = queue;
PriorityQueue<String> constructedQueue = new PriorityQueue<String>(c);
assertEquals(queue.comparator(), constructedQueue.comparator());
while (queue.size() > 0) {
assertEquals(queue.poll(), constructedQueue.poll());
}
assertEquals(0, constructedQueue.size());
}
public static void main (String [] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int testCaseCount=Integer.parseInt(br.readLine());
for (int testCase=0;testCase<testCaseCount;testCase++) {
br.readLine();
int M=Integer.parseInt(br.readLine());
int N=Integer.parseInt(br.readLine());
int m=0;
PriorityQueue<Edge> edges=new PriorityQueue<>();
HashMap<String, Integer> map=new HashMap<>();
for (int n=0;n<N;n++) {
StringTokenizer st=new StringTokenizer(br.readLine());
String xs=st.nextToken();
if (!map.containsKey(xs)) map.put(xs, m++);
String ys=st.nextToken();
if (!map.containsKey(ys)) map.put(ys, m++);
edges.offer(new Edge(map.get(xs), map.get(ys), Integer.parseInt(st.nextToken())));
}
System.out.println(mst(M, edges));
if (testCase<testCaseCount-1) System.out.println();
}
}
/**
* java.util.PriorityQueue#Clear()
*/
public void test_clear() {
PriorityQueue<Integer> integerQueue = new PriorityQueue<Integer>();
int[] array = { 2, 45, 7, -12, 9 };
for (int i = 0; i < array.length; i++) {
integerQueue.offer(array[i]);
}
integerQueue.clear();
assertTrue(integerQueue.isEmpty());
}
private void setShortcuts() {
if (Build.VERSION.SDK_INT < Build.VERSION_CODES.N_MR1) return;
PriorityQueue<Class<? extends Fragment>> queue = new PriorityQueue<>(
(o1, o2) -> {
int opened1 = AppSettings.getFragmentOpened(o1, this);
int opened2 = AppSettings.getFragmentOpened(o2, this);
return opened2 - opened1;
});
for (Map.Entry<Integer, Class<? extends Fragment>> entry : mActualFragments.entrySet()) {
Class<? extends Fragment> fragmentClass = entry.getValue();
if (fragmentClass == null || fragmentClass == SettingsFragment.class) continue;
queue.offer(fragmentClass);
}
List<ShortcutInfo> shortcutInfos = new ArrayList<>();
ShortcutManager shortcutManager = getSystemService(ShortcutManager.class);
shortcutManager.removeAllDynamicShortcuts();
for (int i = 0; i < 4; i++) {
NavigationFragment fragment = findNavigationFragmentByClass(queue.poll());
if (fragment == null || fragment.mFragmentClass == null) continue;
Intent intent = new Intent(this, MainActivity.class);
intent.setAction(Intent.ACTION_VIEW);
intent.putExtra(INTENT_SECTION, fragment.mFragmentClass.getCanonicalName());
intent.addFlags(Intent.FLAG_ACTIVITY_NEW_TASK | Intent.FLAG_ACTIVITY_CLEAR_TOP);
ShortcutInfo shortcut = new ShortcutInfo.Builder(this,
fragment.mFragmentClass.getSimpleName())
.setShortLabel(getString(fragment.mId))
.setLongLabel(Utils.strFormat(getString(R.string.open), getString(fragment.mId)))
.setIcon(Icon.createWithResource(this, fragment.mDrawable == 0 ?
R.drawable.ic_blank : fragment.mDrawable))
.setIntent(intent)
.build();
shortcutInfos.add(shortcut);
}
shortcutManager.setDynamicShortcuts(shortcutInfos);
}
/**
* java.util.PriorityQueue#remove(Object)
*/
public void test_remove_Ljava_lang_Object_using_comparator() {
PriorityQueue<String> queue = new PriorityQueue<String>(10,
new MockComparatorStringByLength());
String[] array = { "AAAAA", "AA", "AAAA", "AAAAAAAA" };
for (int i = 0; i < array.length; i++) {
queue.offer(array[i]);
}
assertFalse(queue.contains("BB"));
assertTrue(queue.remove("AA"));
}
private PriorityQueue<Long> getSortedTimestamps() throws Exception {
PriorityQueue<Long> sortedTimestamps = new PriorityQueue<>();
for (Long timestamp : elementQueueState.keys()) {
sortedTimestamps.offer(timestamp);
}
return sortedTimestamps;
}
private void setShortcuts() {
if (Build.VERSION.SDK_INT < Build.VERSION_CODES.N_MR1) return;
PriorityQueue<Class<? extends Fragment>> queue = new PriorityQueue<>(
(o1, o2) -> {
int opened1 = AppSettings.getFragmentOpened(o1, this);
int opened2 = AppSettings.getFragmentOpened(o2, this);
return opened2 - opened1;
});
for (Map.Entry<Integer, Class<? extends Fragment>> entry : mActualFragments.entrySet()) {
Class<? extends Fragment> fragmentClass = entry.getValue();
if (fragmentClass == null || fragmentClass == SettingsFragment.class) continue;
queue.offer(fragmentClass);
}
List<ShortcutInfo> shortcutInfos = new ArrayList<>();
ShortcutManager shortcutManager = getSystemService(ShortcutManager.class);
shortcutManager.removeAllDynamicShortcuts();
for (int i = 0; i < 4; i++) {
NavigationFragment fragment = findNavigationFragmentByClass(queue.poll());
if (fragment == null || fragment.mFragmentClass == null) continue;
Intent intent = new Intent(this, MainActivity.class);
intent.setAction(Intent.ACTION_VIEW);
intent.putExtra(INTENT_SECTION, fragment.mFragmentClass.getCanonicalName());
intent.addFlags(Intent.FLAG_ACTIVITY_NEW_TASK | Intent.FLAG_ACTIVITY_CLEAR_TOP);
ShortcutInfo shortcut = new ShortcutInfo.Builder(this,
fragment.mFragmentClass.getSimpleName())
.setShortLabel(getString(fragment.mId))
.setLongLabel(Utils.strFormat(getString(R.string.open), getString(fragment.mId)))
.setIcon(Icon.createWithResource(this, fragment.mDrawable == 0 ?
R.drawable.ic_blank : fragment.mDrawable))
.setIntent(intent)
.build();
shortcutInfos.add(shortcut);
}
shortcutManager.setDynamicShortcuts(shortcutInfos);
}
/**
* offer(null) throws NPE
*/
public void testOfferNull() {
PriorityQueue q = new PriorityQueue(1);
try {
q.offer(null);
shouldThrow();
} catch (NullPointerException success) {}
}
/**
* Heap. Merge.
* Just like how we merge 2 sorted arrays, we can do the same to N arrays.
* The only difference is that a min-heap is needed to find the next minimum.
* Note that the median depends on whether we have odd or even total numbers, N.
* If N is odd, median is the number at N / 2 + 1.
* E.g. N = 7, N/2 = 3, the 4th number is the median.
* If N is even, median is the average of N / 2 and N / 2 + 1.
* E.g. N = 8, N/2 = 4, the average of 4th and 5th is the median.
*/
public double getMedian(int[][] arrs) {
if (arrs.length == 0) return 0;
// int[] is {row, column, value}
PriorityQueue<int[]> pq = new PriorityQueue<>(arrs.length, Comparator.comparingInt(a -> a[2]));
int n = 0; // Total number of integers.
for (int i = 0; i < arrs.length; i++) {
pq.offer(new int[]{i, 0, arrs[i][0]});
n += arrs[i].length;
}
double median = 0;
for (int i = 0; i < n / 2; i++) { // Loop n / 2 times.
// Get min from heap, then add its next to heap if there is one.
int[] min = pq.poll();
if (min[1] < arrs[min[0]].length - 1) {
min[1]++;
min[2] = arrs[min[0]][min[1]];
pq.offer(min);
}
if (i == n / 2 - 2 && n % 2 == 0) { // When n is even, record the last 2 values.
median = min[2];
} else if (i == n / 2 - 1 && n % 2 == 0) {
median = (median + min[2]) / 2;
} else if (i == n / 2 - 1 && n % 2 == 1) { // When n is odd, poll one more value at the last iteration.
median = pq.poll()[2];
}
}
return median;
}
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();
}