下面列出了java.util.PriorityQueue#remove ( ) 实例代码,或者点击链接到github查看源代码,也可以在右侧发表评论。
public void restoreModels(Map<CharacterInfoTab, ModelMap> states, int selectedIndex)
{
CharacterInfoTab firstTab = (CharacterInfoTab) getComponentAt(selectedIndex);
restoreTab(firstTab, states.get(firstTab));
int oldSelectedIndex = getSelectedIndex();
setSelectedIndex(selectedIndex);
if (oldSelectedIndex == selectedIndex)
{
handleDisplayAware();
}
PriorityQueue<CharacterInfoTab> queue = new PriorityQueue<>(states.keySet().size(), this);
queue.addAll(states.keySet());
queue.remove(firstTab);
while (!queue.isEmpty())
{
CharacterInfoTab infoTab = queue.poll();
ModelMap models = states.get(infoTab);
restoreQueue.add(submit(new RestoreModelsTask(infoTab, models)));
}
}
public static ArrayList<Long> primeFactorization(long n) {
ArrayList<Long> factors = new ArrayList<>();
if (n <= 0) throw new IllegalArgumentException();
else if (n == 1) return factors;
PriorityQueue<Long> divisorQueue = new PriorityQueue<>();
divisorQueue.add(n);
while (!divisorQueue.isEmpty()) {
long divisor = divisorQueue.remove();
if (isPrime(divisor)) {
factors.add(divisor);
continue;
}
long next_divisor = pollardRho(divisor);
if (next_divisor == divisor) {
divisorQueue.add(divisor);
} else {
divisorQueue.add(next_divisor);
divisorQueue.add(divisor / next_divisor);
}
}
return factors;
}
@Test
public void testContainmentRandomized() {
for (int i = 0; i < LOOPS; i++) {
List<Integer> randNums = genRandList(100);
PriorityQueue<Integer> PQ = new PriorityQueue<>();
BinaryHeap<Integer> pq = new BinaryHeap<>();
for (int j = 0; j < randNums.size(); j++) {
pq.add(randNums.get(j));
PQ.add(randNums.get(j));
}
for (int j = 0; j < randNums.size(); j++) {
int randVal = randNums.get(j);
assertEquals(pq.contains(randVal), PQ.contains(randVal));
pq.remove(randVal);
PQ.remove(randVal);
assertEquals(pq.contains(randVal), PQ.contains(randVal));
}
}
}
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 relaxEdges(Vertex [] graph,int vertex,int contractId, PriorityQueue queue,int sourceId){
ArrayList<Integer> vertexList = graph[vertex].outEdges;
ArrayList<Long> costList = graph[vertex].outECost;
for(int i=0;i<vertexList.size();i++){
int temp = vertexList.get(i);
long cost = costList.get(i);
if(graph[temp].contracted){
continue;
}
if(checkId(graph,vertex,temp) || graph[temp].distance.distance > graph[vertex].distance.distance + cost){
graph[temp].distance.distance = graph[vertex].distance.distance + cost;
graph[temp].distance.contractId = contractId;
graph[temp].distance.sourceId = sourceId;
queue.remove(graph[temp]);
queue.add(graph[temp]);
}
}
}
static public MinimumSpanningTree build(TreeNode[] nodes, int[][] distances, int root) {
MinimumSpanningTree mst = new MinimumSpanningTree(nodes[root]);
PriorityQueue<Vertex> costList = new PriorityQueue<Vertex>();
for(int i = 0; i < distances.length; i++) {
if(i != root)
costList.add(new Vertex(i, root, distances[i][root]));
}
while(!costList.isEmpty()) {
Vertex next = costList.poll();
nodes[next.to].addChild(nodes[next.id]);
Vertex[] remains = costList.toArray(new Vertex[0]);
for(int i = 0; i<remains.length; i++) {
if(distances[remains[i].id][next.id] <= remains[i].value) {
costList.remove(remains[i]);
remains[i].to = next.id;
remains[i].value = distances[remains[i].id][next.id];
costList.add(remains[i]);
}
}
}
return mst;
}
/**
* retainAll(c) retains only those elements of c and reports true if changed
*/
public void testRetainAll() {
PriorityQueue q = populatedQueue(SIZE);
PriorityQueue p = populatedQueue(SIZE);
for (int i = 0; i < SIZE; ++i) {
boolean changed = q.retainAll(p);
if (i == 0)
assertFalse(changed);
else
assertTrue(changed);
assertTrue(q.containsAll(p));
assertEquals(SIZE - i, q.size());
p.remove();
}
}
private static long lockAndRunQueue(final AsyncServer server, final PriorityQueue<Scheduled> queue) {
long wait = QUEUE_EMPTY;
// find the first item we can actually run
while (true) {
Scheduled run = null;
synchronized (server) {
long now = SystemClock.elapsedRealtime();
if (queue.size() > 0) {
Scheduled s = queue.remove();
if (s.time <= now) {
run = s;
}
else {
wait = s.time - now;
queue.add(s);
}
}
}
if (run == null)
break;
run.run();
}
server.postCounter = 0;
return wait;
}
public void remove(PrioritizedSplitRunner split)
{
checkArgument(split != null, "split is null");
lock.lock();
try {
for (PriorityQueue<PrioritizedSplitRunner> level : levelWaitingSplits) {
level.remove(split);
}
}
finally {
lock.unlock();
}
}
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;
}
/**
* size changes when elements added and removed
*/
public void testSize() {
PriorityQueue q = populatedQueue(SIZE);
for (int i = 0; i < SIZE; ++i) {
assertEquals(SIZE - i, q.size());
q.remove();
}
for (int i = 0; i < SIZE; ++i) {
assertEquals(i, q.size());
q.add(new Integer(i));
}
}
/**
* Removes an item to the global queue and updates its upload status.
*
* @param c the current context
* @param queue the queue to update from
* @param procedureUri the procedure in the queue
* @param newStatus the new upload status
* @return true if the procedure was in the queue and updated
*/
public static boolean removeFromQueue(Context c, PriorityQueue<Uri> queue,
Uri procedureUri, int newStatus) {
if (QueueManager.isInQueue(queue, procedureUri)) {
queue.remove(procedureUri);
QueueManager.updateQueueInDB(c, queue);
QueueManager.setProcedureUploadStatus(c, procedureUri, newStatus);
return true;
}
return false;
}
/**
* Performs a depth first search (without backtracking) starting from the the given transformation
* @param queue
* @param transformation
*/
private void dfs(PriorityQueue<Object> queue, Transformation<?> transformation) {
if (mustStop()) {
return;
}
Transformation<?> next = expand(queue, transformation);
if (next != null) {
queue.remove(next.getIdentifier());
dfs(queue, next);
}
}
@Override
public Iterator<IntermediateSampleData<T>> sampleInPartition(Iterator<T> input) {
if (numSamples == 0) {
return emptyIntermediateIterable;
}
// This queue holds fixed number elements with the top K weight for current partition.
PriorityQueue<IntermediateSampleData<T>> queue = new PriorityQueue<IntermediateSampleData<T>>(numSamples);
int index = 0;
IntermediateSampleData<T> smallest = null;
while (input.hasNext()) {
T element = input.next();
if (index < numSamples) {
// Fill the queue with first K elements from input.
queue.add(new IntermediateSampleData<T>(random.nextDouble(), element));
smallest = queue.peek();
} else {
double rand = random.nextDouble();
// Remove the element with the smallest weight, and append current element into the queue.
if (rand > smallest.getWeight()) {
queue.remove();
queue.add(new IntermediateSampleData<T>(rand, element));
smallest = queue.peek();
}
}
index++;
}
return queue.iterator();
}
@Test
public void testRandomizedRemoving() {
for (int i = 0; i < LOOPS; i++) {
int sz = i;
List<Integer> randNums = genRandList(sz);
PriorityQueue<Integer> pq1 = new PriorityQueue<>();
BinaryHeap<Integer> pq2 = new BinaryHeap<>();
// 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));
}
}
}
/**
* Replace a given path with that of this candidate move.
*
* @param openMap The list of available nodes.
* @param openMapQueue The queue of available nodes.
* @param f The heuristic values for A*.
* @param sh A {@code SearchHeuristic} to apply.
*/
public void improve(HashMap<String, PathNode> openMap,
PriorityQueue<PathNode> openMapQueue,
HashMap<String, Integer> f,
SearchHeuristic sh) {
PathNode best = openMap.get(dst.getId());
if (best != null) {
openMap.remove(dst.getId());
openMapQueue.remove(best);
}
add(openMap, openMapQueue, f, sh);
}
@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));
}
}
}
public void computeCOF(ArrayList<COFObject> cofobjectList, int k, DistanceMeasure measure) {
// define a list of knn for each cof object
PriorityQueue<COFKnn> knnList = new PriorityQueue<COFKnn>();
// reset pcl, kDist, and deviation
double pcl = 0.0;
double kDist = 0.0;
double deviation = 0.0;
for (COFObject cofobject : cofobjectList) {// for all objects in the dataset
double distance = Double.POSITIVE_INFINITY;
// compute the distance to current object
distance = measure.calculateDistance(this.getValues(), cofobject.getValues());
COFKnn cOFKnn = new COFKnn(cofobject, distance);
// determine if cofobject is on of the nearest neighbors to current object
if (knnList.size() < k) {
knnList.offer(cOFKnn);
} else if (distance < knnList.peek().getDistance()) {
knnList.remove();
knnList.offer(cOFKnn);
}
// if the cofobject has the same class label, add its distance to deviation
if (this.getLabel() == cofobject.getLabel()) {
deviation += distance;
}
}
this.setDeviation(deviation); // save deviation
// compute pcl to current object
for (COFKnn cofKnn : knnList) {
kDist += measure.calculateDistance(getValues(), cofKnn.getCofobject().getValues());
if (this.getLabel() == cofKnn.getCofobject().getLabel()) {
pcl++;
}
}
this.setPcl(pcl); // save pcl
this.setCOF(pcl); // save the initial cof based on pcl
this.setKDist(kDist); // save kDist
}
/**
* Sample algorithm for the second phase. This operation should be executed as the UDF of
* an all reduce operation.
*
* @param input The intermediate sample output generated in the first phase.
* @return The sampled output.
*/
public Iterator<T> sampleInCoordinator(Iterator<IntermediateSampleData<T>> input) {
if (numSamples == 0) {
return emptyIterable;
}
// This queue holds fixed number elements with the top K weight for the coordinator.
PriorityQueue<IntermediateSampleData<T>> reservoir = new PriorityQueue<IntermediateSampleData<T>>(numSamples);
int index = 0;
IntermediateSampleData<T> smallest = null;
while (input.hasNext()) {
IntermediateSampleData<T> element = input.next();
if (index < numSamples) {
// Fill the queue with first K elements from input.
reservoir.add(element);
smallest = reservoir.peek();
} else {
// If current element weight is larger than the smallest one in queue, remove the element
// with the smallest weight, and append current element into the queue.
if (element.getWeight() > smallest.getWeight()) {
reservoir.remove();
reservoir.add(element);
smallest = reservoir.peek();
}
}
index++;
}
final Iterator<IntermediateSampleData<T>> itr = reservoir.iterator();
return new Iterator<T>() {
@Override
public boolean hasNext() {
return itr.hasNext();
}
@Override
public T next() {
return itr.next().getElement();
}
@Override
public void remove() {
itr.remove();
}
};
}
public double[] medianSlidingWindow(int[] nums, int k) {
int len = nums.length;
int windowLen = len - k + 1;
double[] res = new double[windowLen];
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 下一个要填的值
int next = 0;
// 循环不变量:
// 1、maxHeap 的堆顶小于等于 minHeap 的堆顶
// 2、maxHeap.size() = minHeap.size() 或者
// 3、maxHeap.size() = minHeap.size() + 1,这样中位数就在 maxHeap 的堆顶
for (int i = 0; i < len; i++) {
// 步骤 1:加入元素的时候,保持第 1、2、3 点
maxHeap.add(nums[i]);
minHeap.add(maxHeap.poll());
if ((i & 1) == 0) {
// 这个语义太难理解:
// 如果还未添加 nums[i] 之前是偶数,那么添加 nums[i] 的效果是 maxHeap 多 1 个元素
maxHeap.add(minHeap.poll());
}
// 步骤 2:移除窗口外的值,移除滑动窗口的左边界
// 假设修正法:默认是大顶堆移除了一个元素
if (i >= k) {
int removeFrom = 1;
// 如果不是在最小堆,就在最大堆
if (minHeap.contains(nums[i - k])) {
minHeap.remove(nums[i - k]);
removeFrom = 0;
} else {
maxHeap.remove(nums[i - k]);
}
// 步骤 3:保持第 2、3 点
if ((i & 1) == 1 && removeFrom == 1) {
maxHeap.add(minHeap.poll());
}
if ((i & 1) == 0 && removeFrom == 0) {
minHeap.add(maxHeap.poll());
}
}
// 步骤 4:求滑动窗口的中位数
if (i >= k - 1) {
if (maxHeap.size() > minHeap.size()) {
res[next] = maxHeap.peek();
} else {
res[next] = minHeap.peek() / 2.0 + maxHeap.peek() / 2.0;
}
next++;
}
}
return res;
}