如何删除优先级队列的尾部元素？我正在尝试使用优先级队列实现波束搜索，一旦优先级队列已满，我想删除最后一个元素（优先级最低的元素）。
谢谢！
问问题
26396 次
8 回答
6
没有简单的方法。将元素从原始元素复制到新元素，最后一个除外。
PriorityQueue removelast(PriorityQueue pq)
{
PriorityQueue pqnew;
while(pq.size() > 1)
{
pqnew.add(pq.poll());
}
pq.clear();
return pqnew;
}
称为
pq = removelast(pq);
于 2013-02-27T16:44:55.093 回答
6
您可能可以使用 Guava 的MinMaxPriorityQueue来执行此操作。它为队列的两端提供了 peek、poll 和 remove 方法。
另一种选择是编写一个强制边界的队列包装器，类似于这个答案。您需要实施offer、add和addAll检查容量。就像是：
public class BoundedQueue<E> implements Serializable, Iterable<E>, Collection<E>, Queue<E> {
private final Queue<E> queue;
private int capacity;
public BoundedQueue(Queue<E> queue, int capacity) {
this.queue = queue;
this.capacity = capacity;
}
@Override
public boolean offer(E o) {
if (queue.size() >= capacity)
return false;
return queue.add(o);
}
@Override
public boolean add(E o) throws IllegalStateException {
if (queue.size() >= capacity)
throw new IllegalStateException("Queue full"); // same behavior as java.util.ArrayBlockingQueue
return queue.add(o);
}
@Override
public boolean addAll(Collection<? extends E> c) {
boolean changed = false;
for (E o: c)
changed |= add(o);
return changed;
}
// All other methods simply delegate to 'queue'
}
于 2013-02-27T17:13:59.533 回答
4
使用反相比较器并从头部移除。如果你需要头部和尾部，那么你使用了错误的数据结构。
于 2013-02-27T22:17:35.257 回答
2
我认为，PR的用例是，他需要头部，但也想要有一个小PQ，所以想法是去除尾部。
由于 PQ 被实现为映射到数组的二叉树，所以头部始终是后备数组 ( queue[0]) 的第一个元素，但尾部并不总是在数组的末尾，您必须搜索它。
我认为一个不错的方法是将 PQ 子类化并编写以下两种方法：
public class MyPriorityQueue<E> extends PriorityQueue<E>
{
// constructors
public E getTail()
{
// queue.length can be bigger than this.size() !!
Object[] queue = this.toArray();
E tail = (E)queue[0];
Comparator<? super E> comparator = this.comparator();
if (comparator !=null)
for(int i = 1; i < this.size(); i++)
if ( comparator.compare(tail, (E)queue[i]) < 0)
tail = (E)queue[i];
else
for(int j = 1; j < this.size(); j++)
if ( ((Comparable)tail).compareTo( ((Comparable)queue[j]) ) < 0 )
tail = (E)queue[j];
return tail;
}
public E removeTail()
{
E tail = this.getTail();
this.remove(tail);
return tail;
}
}
于 2015-02-02T15:16:23.973 回答
1
当您将数据添加到优先级队列本身时，请进行比较；
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
于 2020-04-12T18:20:20.033 回答
0
如果您有理由不向内存生成另一个元素，则有一个更好的解决方案。
您可以获取队列的大小并在计算要遍历的元素时使用迭代器运行它，一旦您到达最后一个或您正在寻找的那个，您可以使用 PriorityQueue.remove(Object o)
Iterator<E> it = Queue.iterator();
while (it.hasNext()) {
temp<E> = it.next();
counter++;
if (counter == Queue.size()) {
Queue.remove(temp);
}
}
于 2017-11-06T07:36:49.460 回答
0
不支持移除尾部。
你能做的最好的事情是交换元素的顺序，让尾巴变成头，而remove()不是它。
于 2020-07-19T17:09:37.557 回答
-3
如果您关心运行时，我建议您实现自己的队列。我做了以下工作并在我的项目中工作。
1) 从 PriorityQueue -> CustomQueue.java 复制粘贴代码 2) 添加方法 removeLast() 3) 这是我使用的实现（非常少）
public void removeLast() {
if(size == 0) {
return;
}
queue[size - 1] = null;
size--;
}
这样做的原因是 PriorityQueue 的实现使用数组来保存对象。所以“大小”实际上是指向数组中下一个可用点的指针。通过减少它，数组/队列的大小会减少，就好像您要删除最后一个元素一样。
于 2014-03-12T22:06:43.030 回答