下面列出了java.util.PriorityQueue#isEmpty ( ) 实例代码，或者点击链接到github查看源代码，也可以在右侧发表评论。
@Test
public void testHeapify() {
for (int i = 1; i < LOOPS; i++) {
Integer[] lst = genRandArray(i);
BinaryHeap<Integer> pq = new BinaryHeap<>(lst);
PriorityQueue<Integer> pq2 = new PriorityQueue<>(i);
for (int x : lst) pq2.add(x);
assertTrue(pq.isMinHeap(0));
while (!pq2.isEmpty()) {
assertEquals(pq.poll(), pq2.poll());
}
}
}
/**
* Emit the next set of key, value pairs as defined by the child
* RecordReaders and operation associated with this composite RR.
*/
public boolean next(K key, TupleWritable value) throws IOException {
if (jc.flush(value)) {
WritableUtils.cloneInto(key, jc.key());
return true;
}
jc.clear();
K iterkey = createKey();
final PriorityQueue<ComposableRecordReader<K,?>> q = getRecordReaderQueue();
while (!q.isEmpty()) {
fillJoinCollector(iterkey);
jc.reset(iterkey);
if (jc.flush(value)) {
WritableUtils.cloneInto(key, jc.key());
return true;
}
jc.clear();
}
return false;
}
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> queue = new PriorityQueue<>(new ListNodeComparator());
ListNode dummy = new ListNode(0);
Arrays.stream(lists).parallel().filter(Objects::nonNull).forEach(queue::add);
ListNode current = dummy;
while (!queue.isEmpty()) {
ListNode minList = queue.poll();
current.next = minList;
if (minList.next != null) {
queue.add(minList.next);
}
minList.next = null;
current = current.next;
}
return dummy.next;
}
public static List<Integer> mergeSorted(List<List<Integer>> sortedArrays) {
List<Iterator<Integer>> iters = new ArrayList<>(sortedArrays.size());
for (List<Integer> array : sortedArrays)
iters.add(array.iterator());
PriorityQueue<ArrayEntry> minHeap = new PriorityQueue<>(iters.size(), ArrayEntry::compareTo);
for (int i = 0; i < iters.size(); i++) {
if (iters.get(i).hasNext())
minHeap.add(new ArrayEntry(iters.get(i).next(),i));
}
List<Integer> result = new ArrayList<>();
while (!minHeap.isEmpty()) {
ArrayEntry temp = minHeap.poll();
result.add(temp.value);
if (iters.get(temp.arrayId).hasNext())
minHeap.add(new ArrayEntry(iters.get(temp.arrayId).next(),temp.arrayId));
}
return result;
}
@Test
public void testPriorityQueueSizeParam() {
for (int i = 1; i < LOOPS; i++) {
Integer[] lst = genRandArray(i);
MinDHeap<Integer> pq = new MinDHeap<>(i, lst.length);
PriorityQueue<Integer> pq2 = new PriorityQueue<>(i);
for (int x : lst) {
pq2.add(x);
pq.add(x);
}
while (!pq2.isEmpty()) assertEquals(pq.poll(), pq2.poll());
}
}
/**
* Emit the next set of key, value pairs as defined by the child
* RecordReaders and operation associated with this composite RR.
*/
public boolean next(K key, TupleWritable value) throws IOException {
if (jc.flush(value)) {
WritableUtils.cloneInto(key, jc.key());
return true;
}
jc.clear();
K iterkey = createKey();
final PriorityQueue<ComposableRecordReader<K,?>> q = getRecordReaderQueue();
while (!q.isEmpty()) {
fillJoinCollector(iterkey);
jc.reset(iterkey);
if (jc.flush(value)) {
WritableUtils.cloneInto(key, jc.key());
return true;
}
jc.clear();
}
return false;
}
public boolean isPossibleDivide(int[] nums, int k) {
int len = nums.length;
if (len % k != 0) {
return false;
}
PriorityQueue<Integer> minHeap = new PriorityQueue<>(len);
for (int num : nums) {
minHeap.offer(num);
}
while (!minHeap.isEmpty()) {
Integer top = minHeap.poll();
for (int i = 1; i < k; i++) {
// 从 1 开始，正好需要移除 k - 1 个元素
// i 正好就是相对于 top 的偏移
if (!minHeap.remove(top + i)) {
// 如果移除失败，说明划分不存在，直接返回 false 即可
return false;
}
}
}
return true;
}
private void kruskals() {
if (solved) return;
// Heapify operation in constructor transforms list of edges into a binary heap in O(n)
PriorityQueue<Edge> pq = new PriorityQueue<>(edges);
UnionFind uf = new UnionFind(n);
int index = 0;
mst = new Edge[n - 1];
while (!pq.isEmpty()) {
// Use heap to poll the next cheapest edge. Polling avoids the need to sort
// the edges before loop in the event that the algorithm terminates early.
Edge edge = pq.poll();
// Skip this edge to avoid creating a cycle in MST.
if (uf.connected(edge.u, edge.v)) continue;
// Include this edge
uf.union(edge.u, edge.v);
mstCost += edge.cost;
mst[index++] = edge;
// Stop early if we found a MST that includes all the nodes.
if (uf.size(0) == n) break;
}
mstExists = (uf.size(0) == n);
solved = true;
}
/**
* Emit the next set of key, value pairs as defined by the child
* RecordReaders and operation associated with this composite RR.
*/
public boolean nextKeyValue()
throws IOException, InterruptedException {
if (key == null) {
key = createKey();
}
if (jc.flush(value)) {
ReflectionUtils.copy(conf, jc.key(), key);
return true;
}
jc.clear();
if (value == null) {
value = createValue();
}
final PriorityQueue<ComposableRecordReader<K,?>> q =
getRecordReaderQueue();
K iterkey = createKey();
while (q != null && !q.isEmpty()) {
fillJoinCollector(iterkey);
jc.reset(iterkey);
if (jc.flush(value)) {
ReflectionUtils.copy(conf, jc.key(), key);
return true;
}
jc.clear();
}
return false;
}
@Test
public void testRandomizedRemoving() {
for (int i = 0; i < LOOPS; i++) {
int sz = i;
List<Integer> randNums = genRandList(sz);
PriorityQueue<Integer> pq1 = new PriorityQueue<>();
BinaryHeapQuickRemovals<Integer> pq2 = new BinaryHeapQuickRemovals<>();
// Add all the elements to both priority queues
for (Integer value : randNums) {
pq1.offer(value);
pq2.add(value);
}
Collections.shuffle(randNums);
int index = 0;
while (!pq1.isEmpty()) {
int removeNum = randNums.get(index++);
assertTrue(pq2.isMinHeap(0));
assertEquals(pq1.size(), pq2.size());
assertEquals(pq1.peek(), pq2.peek());
pq1.remove(removeNum);
pq2.remove(removeNum);
assertEquals(pq1.peek(), pq2.peek());
assertEquals(pq1.size(), pq2.size());
assertTrue(pq2.isMinHeap(0));
}
}
}
/** {@inheritDoc} */
public boolean nextKeyValue() throws IOException, InterruptedException {
if (key == null) {
key = createKey();
}
if (value == null) {
value = createValue();
}
if (jc.flush(ivalue)) {
ReflectionUtils.copy(conf, jc.key(), key);
ReflectionUtils.copy(conf, emit(ivalue), value);
return true;
}
if (ivalue == null) {
ivalue = createTupleWritable();
}
jc.clear();
final PriorityQueue<ComposableRecordReader<K,?>> q =
getRecordReaderQueue();
K iterkey = createKey();
while (q != null && !q.isEmpty()) {
fillJoinCollector(iterkey);
jc.reset(iterkey);
if (jc.flush(ivalue)) {
ReflectionUtils.copy(conf, jc.key(), key);
ReflectionUtils.copy(conf, emit(ivalue), value);
return true;
}
jc.clear();
}
return false;
}
static public Result chooseAndBuildLine(TreeNode[] nodes, int[][] distances,
int root, int nodeNumber) {
PriorityQueue<Vertex> costList = new PriorityQueue<Vertex>();
int[] locationsChoosed = new int[nodeNumber];
Arrays.fill(locationsChoosed, -1);
int totalWeight = 0;
for (int i = 0; i < distances.length; i++) {
if (i != root)
costList.add(new Vertex(i, root, distances[i][root]));
}
int number = 0;
while ((number < nodeNumber) && (!costList.isEmpty())) {
Vertex next = costList.poll();
nodes[next.to].addChild(nodes[next.id]);
totalWeight += next.value;
//LOG.info("NTar: add " + nodes[next.id] + " as child of " + nodes[next.to]);
locationsChoosed[number] = next.id;
number = number + 1;
Vertex[] remains = costList.toArray(new Vertex[0]);
for (int i = 0; i<remains.length; i++) {
costList.remove(remains[i]);
remains[i].to = next.id;
remains[i].value = distances[remains[i].id][next.id];
costList.add(remains[i]);
}
}
return new Result(totalWeight, locationsChoosed);
}
private static int[] djikstra(int from, ArrayList<Edge> [] adjList) {
PriorityQueue<Edge> q=new PriorityQueue<>();
q.offer(new Edge(from,from,0));
int [] maxDist=new int [adjList.length];
Arrays.fill(maxDist, NOEDGE);
maxDist[from]=0;
while (!q.isEmpty()) {
Edge e=q.poll();
for (Edge next : adjList[e.dest]) if (e.cost+next.cost<maxDist[next.dest]) {
maxDist[next.dest]=e.cost+next.cost;
q.offer(new Edge(e.src,next.dest,maxDist[next.dest]));
}
}
return maxDist;
}
@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());
}
}
}
protected RegressionTree buildDepthLimitedTree(Instances instances, int maxDepth) {
RegressionTree tree = new RegressionTree();
final int limit = 5;
// stats[0]: totalWeights
// stats[1]: sum
// stats[2]: weightedMean
// stats[3]: splitEval
double[] stats = new double[4];
if (maxDepth <= 0) {
getStats(instances, stats);
tree.root = new RegressionTreeLeaf(stats[1]);
return tree;
}
Map<TreeNode, Dataset> datasets = new HashMap<>();
Map<TreeNode, Integer> depths = new HashMap<>();
Dataset dataset = null;
if (this.cache != null) {
dataset = Dataset.create(this.cache, instances);
} else {
dataset = Dataset.create(instances);
}
tree.root = createNode(dataset, limit, stats);
PriorityQueue<Element<TreeNode>> q = new PriorityQueue<>();
q.add(new Element<TreeNode>(tree.root, stats[2]));
datasets.put(tree.root, dataset);
depths.put(tree.root, 0);
while (!q.isEmpty()) {
Element<TreeNode> elemt = q.remove();
TreeNode node = elemt.element;
Dataset data = datasets.get(node);
int depth = depths.get(node);
if (!node.isLeaf()) {
TreeInteriorNode interiorNode = (TreeInteriorNode) node;
Dataset left = new Dataset(data.instances);
Dataset right = new Dataset(data.instances);
split(data, interiorNode, left, right);
if (depth >= maxDepth - 1) {
getStats(left.instances, stats);
interiorNode.left = new RegressionTreeLeaf(stats[2]);
getStats(right.instances, stats);
interiorNode.right = new RegressionTreeLeaf(stats[2]);
} else {
interiorNode.left = createNode(left, limit, stats);
if (!interiorNode.left.isLeaf()) {
q.add(new Element<TreeNode>(interiorNode.left, stats[3]));
datasets.put(interiorNode.left, left);
depths.put(interiorNode.left, depth + 1);
}
interiorNode.right = createNode(right, limit, stats);
if (!interiorNode.right.isLeaf()) {
q.add(new Element<TreeNode>(interiorNode.right, stats[3]));
datasets.put(interiorNode.right, right);
depths.put(interiorNode.right, depth + 1);
}
}
}
}
return tree;
}
public static void main (String [] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int testCaseCount=Integer.parseInt(br.readLine());
int [][] delta= {{-1,0},{1,0},{0,-1},{0,1}};
for (int testCase=0;testCase<testCaseCount;testCase++) {
int N=Integer.parseInt(br.readLine());
int M=Integer.parseInt(br.readLine());
int [][] cost=new int [N][M];
int [][] lowestCost=new int [N][M];
for (int i=0;i<N;i++) {
StringTokenizer st=new StringTokenizer(br.readLine());
for (int i2=0;i2<M;i2++) {
cost[i][i2]=Integer.parseInt(st.nextToken());
lowestCost[i][i2]=Integer.MAX_VALUE;
}
}
PriorityQueue<Edge> queue=new PriorityQueue<>();
queue.offer(new Edge(0, 0, cost[0][0]));
lowestCost[0][0]=cost[0][0];
while (!queue.isEmpty()) {
Edge e=queue.poll();
if (e.destx==N-1 && e.desty==M-1) break;
for (int i=0;i<delta.length;i++) {
int x=e.destx+delta[i][0];
int y=e.desty+delta[i][1];
if (x>=0 && x<N && y>=0 && y<M) {
int newCost=cost[x][y]+e.cost;
if (newCost<lowestCost[x][y]) {
lowestCost[x][y] = newCost;
queue.offer(new Edge(x,y,newCost));
}
}
}
}
System.out.println(lowestCost[cost.length-1][cost[0].length-1]);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
PriorityQueue<Student> data = new PriorityQueue<Student>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
if (o1.getCgpa() < o2.getCgpa()) {
return 1;
} else if (o1.getCgpa() > o2.getCgpa()) {
return -1;
} else {
if (o1.getFname().compareTo(o2.getFname()) == 0) {
if (o1.getToken() > o2.getToken()) {
return 1;
} else if (o1.getToken() < o2.getToken()) {
return -1;
} else {
return 0;
}
} else {
return o1.getFname().compareTo(o2.getFname());
}
}
}
});
for (int i = 0; i < t; i++) {
String op = sc.next();
switch (op) {
case "ENTER":
String name = sc.next();
double cgpa = sc.nextDouble();
int id = sc.nextInt();
Student s = new Student(id, name, cgpa);
data.add(s);
break;
case "SERVED":
if (data.isEmpty()) {
break;
}
data.remove();
}
}
if (data.isEmpty())
System.out.println("EMPTY");
else {
while (!data.isEmpty()) {
Student st = data.poll();
System.out.println(st.getFname());
}
}
sc.close();
}
public void render() {
Renderer.pushMatrix();
Renderer.scale(2, 2);
Renderer.render(bg, 0, 0, 1, 1, 0, 0, 240, 160, 1);
Renderer.drawRectangle(0, 0, 240, 160, 1, new Color(0,0,0,darkness));
if (shakeTimer > 0) {
shakeTimer -= Game.getDeltaSeconds();
if (prevShakeTimer - shakeTimer > SHAKE_INTERVAL) {
float factor = Math.min(shakeTimer * 1.2f, 1.0f);
shakeX *= -factor;
shakeY *= -factor;
prevShakeTimer = shakeTimer;
}
if (shakeTimer < 0) {
shakeTimer = 0;
prevShakeTimer = 0;
shakeX = 0;
shakeY = 0;
}
}
// Shake
Renderer.translate((int) shakeX, (int) shakeY);
SortByRender comparator = new SortByRender();
PriorityQueue<Entity> renderQueue = new PriorityQueue<Entity>(entities.size()+1, comparator);
renderQueue.addAll(entities);
while(!renderQueue.isEmpty()) {
Entity e = renderQueue.poll();
Renderer.pushMatrix();
if(e.renderDepth > HUD_DEPTH && !(e instanceof BackgroundEffect)) {
Renderer.translate(cameraOffset, 0);
}
e.render();
Renderer.popMatrix();
}
// Undo shake translation
Renderer.popMatrix();
Renderer.removeClip();
}
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;
}
@FunctionSpec(name = "getpreviousversion", returnType = "array of ChangedFile", formalParameters = { "CodeRepository", "ChangedFile" })
public static ChangedFile[] getPreviousVersion(final CodeRepository cr, final ChangedFile cf) throws Exception {
List<ChangedFile> l = new ArrayList<ChangedFile>();
for (int i = 0; i < cf.getChangesCount(); i++) {
ChangeKind kind = cf.getChanges(i);
if (kind == ChangeKind.ADDED || kind == ChangeKind.COPIED)
continue;
ChangedFile.Builder fb = ChangedFile.newBuilder(cf);
if (!cf.getPreviousNames(i).isEmpty())
fb.setName(cf.getPreviousNames(i));
ChangedFile key = fb.build();
int revisionIndex = cf.getPreviousVersions(i);
Set<Integer> queuedRevisionIds = new HashSet<Integer>();
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(100, new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
return i2 - i1;
}
});
pq.offer(revisionIndex);
queuedRevisionIds.add(revisionIndex);
while (!pq.isEmpty()) {
revisionIndex = pq.poll();
Revision rev = getRevision(cr, revisionIndex);
int index = Collections.binarySearch(rev.getFilesList(), key, new Comparator<ChangedFile>() {
@Override
public int compare(ChangedFile f1, ChangedFile f2) {
return f1.getName().compareTo(f2.getName());
}
});
if (index >= 0) {
ChangedFile ocf = rev.getFiles(index);
if (ocf.getChange() != ChangeKind.DELETED)
l.add(ocf);
} else {
for (int parentId : rev.getParentsList()) {
if (!queuedRevisionIds.contains(parentId)) {
pq.offer(parentId);
queuedRevisionIds.add(parentId);
}
}
}
}
}
return l.toArray(new ChangedFile[0]);
}