标签: priority-queue

PriorityQueue如果你不能insertWithPriority,他们为什么命名？它看起来非常类似于堆.有什么不同吗？如果没有区别,那为什么它被命名PriorityQueue而不是Heap？

我正在开发一个演示Djikstra算法的应用程序,并且要使用它,我需要在我的元素值减少时恢复堆属性.

关于复杂的问题是,当算法改变的元素的值,该元素的索引用于优先级队列中的内部结构(堆在这种情况下)是未知的.因此,我之前需要进行O(n)搜索,以便恢复索引,然后才能对其执行实际的减少键.

而且,我不确定操作所需的实际代码.我在这里使用D-Heap 作为我的优先级队列.伪代码会有所帮助,但我更喜欢Java中的一个例子,说明应该如何做.

相关问题:

• 具有固定大小的Java PriorityQueue
• 我如何使用PriorityQueue？
• 获取数组中n个最小元素的索引
• Scala:有没有像我在Java中那样使用PriorityQueue的方法？

我有一个非常大的数据集(超过500万件),我需要从中获得N个最大的项目.最自然的方法是使用堆/优先级队列,只存储前N个项目.JVM(Scala/Java)的优先级队列有几个很好的实现,即:

• scala.collection.mutable.PriorityQueue
• java.util.PriorityQueue中
• lucene.util.PriorityQueue

前2个很好,但它们存储了所有项目,在我的情况下会产生关键的内存开销.第三个(Lucene实现)没有这样的缺点,但正如我从文档中看到的那样,它也不支持自定义比较器,这对我来说没用.

所以,我的问题是:是否有PriorityQueue实现与固定容量和自定义比较？

UPD.最后,根据Peter的回答,我创建了自己的实现:

public class FixedSizePriorityQueue<E> extends TreeSet<E> {

    private int elementsLeft;

    public FixedSizePriorityQueue(int maxSize) {
        super(new NaturalComparator());
        this.elementsLeft = maxSize;
    }

    public FixedSizePriorityQueue(int maxSize, Comparator<E> comparator) {
        super(comparator);
        this.elementsLeft = maxSize;
    }


    /**
     * @return true if element was added, false otherwise
     * */
    @Override
    public boolean add(E e) {
        if (elementsLeft == 0 && …

我有以下错误的代码,我试图在VC2010中编译,但我得到错误C2974这只发生在我包含lambda表达式时,所以我猜它与此有关.

typedef pair<pair<int, int>, int> adjlist_edge;
priority_queue< adjlist_edge , vector<adjlist_edge>,
    [](adjlist_edge a, adjlist_edge b) -> bool {
        if(a.second > b.second){ return true; } else { return false; }
    }> adjlist_pq;

我知道模板定义的形式是正确的

priority_queue<int , vector<int>, greater<int>> pq;

按预期工作.我有什么想法我做错了吗？看起来不对的lambda有什么明显的错误我可能会忽略吗？谢谢阅读!

一旦PriorityQueue中对象的优先级发生变化,Java是否有一种简单的方法来重新评估堆？我找不到它的任何迹象Javadoc,但必须有办法以某种方式做到这一点,对吧？我正在删除该对象,然后重新添加它,但这显然比在堆上运行更新要慢.

我有一个应用程序(C++),我认为STL将很好地服务priority_queue. 文件说:

Priority_queue是一个容器适配器,这意味着它是在一些底层容器类型之上实现的.默认情况下,底层类型是vector,但可以显式选择其他类型.

和

优先级队列是标准概念,可以通过多种不同方式实现; 这个实现使用堆.

我以前认为那top()是O(1),那push()将是一个O(logn)(我首先选择的两个原因priority_queue) - 但文档既没有证实也没有否定这个假设.

深入挖掘,序列概念的文档说:

单元素插入和擦除的复杂性依赖于序列.

在priority_queue使用vector作为堆,其(默认):

...支持随机访问元素,在末尾插入和删除元素,以及在开头或中间插入和删除元素的线性时间.

我推断,使用默认的priority_queue,top()是O(1)和push()是O(n).

问题1:这是正确的吗？(top()访问是O(1)和push()是O(n)？)

问题2:如果我使用(或)而不是a 来实现,我是否能够实现O(logn)效率？这样做的后果是什么？其他什么操作会受到影响？push()setmultisetvectorpriority_queue

NB:我担心时间效率,而不是空间.

在蟒蛇有一个内置的heapq算法,让你push,pop,nlargest,nsmallest...等,你可以申请名单.但是,也有queue.PriorityQueue类似乎支持或多或少相同的功能.有什么区别,你何时会使用另一个？

我正在计算一个algortihm的大量可能的结果组合.要对这些组合进行排序,我使用双倍值对它们进行评级,并将它们存储在PriorityQueue中.目前,该队列中有大约20万个项目,这几乎是内存集成.实际上,我只需要说出列表中所有项目中最好的1000或100.所以我开始问自己是否有办法在Java中拥有一个固定大小的优先级队列.我的行为应该是这样的:物品是否比已存储的物品更好？如果是,请将其插入相应的位置并抛出最小等级的元素.

有没有人有想法？再次感谢!

马尔科

我有一个对象的priority_queue:

typedef priority_queue<Object> Queue;
Queue queue;

有时,其中一个对象的优先级可能会发生变化 - 我需要能够以有效的方式更新队列中该对象的优先级.目前我使用的方法虽然有效,但看起来效率低下:

Queue newQueue;
while (!queue.empty())
{
  Object obj=queue.top();
  queue.pop();

  if (priorityHasChanged(obj))
    newQueue.push_back(Object(new_priority));
  else
    newQueue.push_back(obj);
}

newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
                 // class and exposed a swap method that swaps in the container

我是这样实现的,因为我当时有点匆忙,这是我能做的最快的事情,我可以确定它能正常工作.不过必须有比这更好的方法.真的我想要的是一种方式:

• 使用更改的优先级提取实例,并插入具有新优先级值的新实例
• 使用更改的优先级更新实例,然后更新队列以便正确排序

做这个的最好方式是什么？

for (Event e : pq)

不按优先级顺序迭代.

while(!pq.isEmpty()){
  Event e = pq.poll();
}

这可以工作但排空队列.