标签: priority-queue

这直接来自Java Docs:

该类及其迭代器实现了Collection和Iterator接口的所有可选方法.方法iterator()中提供的迭代器不保证以任何特定顺序遍历优先级队列的元素.如果需要有序遍历,请考虑使用Arrays.sort(pq.toArray()).

基本上,我的PriorityQueue工作正常,但是使用自己内置的toString()方法将其打印到屏幕上会让我看到这个异常现象,并且想知道是否有人可以解释为什么它是迭代器提供的(并且使用过)内部)不按自然顺序遍历PriorityQueue？

请原谅我,如果这是一个尝试过的问题,但我有点难以搞清楚.

我目前有一个类Node,每个'node'都是迷宫中的一个正方形.我正在尝试实现A*算法,因此每个节点都有一个f-cost(int)数据成员.我想知道是否有一种方法可以创建这些节点的优先级队列,并将f-cost变量设置为比较器？

我在网上看了一些例子,但我能找到的只是字符串优先级队列.我可以为Node类实现Comparator吗？这会允许我访问存储在其中的数据成员吗？

非常感谢!

这不是作业.

我正在使用一个小的"优先级队列"(目前实现为数组)来存储具有最小值的最后N个项目.这有点慢 - O(N)项目插入时间.当前实现跟踪数组中的最大项并丢弃任何不适合数组的项,但我仍希望进一步减少操作数.

寻找符合以下要求的优先级队列算法:

1. queue可以实现为数组,它具有固定的大小和_cannot_ grow.严禁在任何队列操作期间进行动态内存分配.
2. 任何不适合数组的东西都会被丢弃,但是队列会保留所有遇到的最小元素.
3. O(log(N))插入时间(即将元素添加到队列中应占用O(log(N))).
4. (可选)O(1)访问队列中最大*项目(队列存储*最小*项目,因此最大项目将首先被丢弃,我需要它们来减少操作次数)
5. 易于实施/理解.理想情况下 - 类似于二元搜索的东西 - 一旦你理解它,你就会永远记住它.
6. 元素无需以任何方式排序.我只需要保持N遇到的最小值.当我需要它们时,我会立刻访问它们.所以从技术上讲,它不必是一个队列,我只需要存储N个最后的最小值.

我最初考虑使用二进制堆(它们可以通过数组轻松实现),但显然当数组不能再增长时它们表现不佳.链接列表和数组将需要额外的时间来移动东西.stl优先级队列增长并使用动态分配(尽管我可能错了).

那么,还有其他想法吗？

--EDIT--
我对STL实现不感兴趣.由于大量的函数调用,STL实现(由少数人建议)比当前使用的线性阵列慢一点.

我对优先级队列算法感兴趣,而不是实现.

我正在建立一个离散事件模拟器.维基百科提到有几个通用优先级队列可以在DES中使用.具体来说,它提到日历队列是一个很好的结构.我找到了一个提到日历队列的pdf(从1988年开始),但在大多数情况下我找不到任何关于它们的内容.有人会介意解释什么是Calendar Queue,它们是如何使用的,以及我可能会在哪里找到示例实现？

我想做这样的事情:

priority_queue< pair<int, int>, vector<int>, greater<int> > Q;

如果我正在比较的类型是int,这可以正常工作,即:

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

但是,很明显,pair<int, int>没有办法将队列中的对与标准进行比较>.我想知道我应该怎么做？我如何实现重载>或者是否有另一种方法可以创建一对最优pair.second的队列在队列的顶部？

是否有可用于Haskell的Fibonacci堆/优先级队列？(或者甚至是渐近更好的一个？)我在这个问题中找到了各种优先级队列实现的列表,但我找不到它们是否满足Fibonacci堆的摊销运行时间:

• Find-minimum是O(1)摊销时间.
• 操作插入,减少键和合并(联合)工作是O(1)摊销时间.
• 操作删除和删除最小值是O(log n)分摊的时间.

参见理论界限的比较.

我正在使用优先级队列来排序和使用大量自定义对象.物体具有"重量",这是它们的自然顺序.但是,插入优先级队列的不同对象可能具有相同的"权重".在这种情况下,我希望优先级队列按照它们放入队列的顺序对它们进行排序.

例如,如果我按顺序添加CustomObjects A,B,C,D,所有具有相同"权重"的优先级队列也应该按顺序返回它们 - 即使我轮询一个或多个对象在加入其他人之前.

这是我的自定义对象的CompareTo:

public int compareTo(CustomObject o) {
    int thisWeight = this.weight;
    int thatWeight = o.weight;
    if(thisWeight < thatWeight){
        return -1;
    }
    else{
        return 1;
    }
}

虽然我认为这将保持初始顺序,但事实并非如此.当我输入重量为1的A,B,C时会发生这种情况; 民意调查A; 并且添加D,E也使用权重1.不知何故,D和E在B之后排序,但在C之前.

我知道PriorityQueues的Iterator没有返回正确的顺序,所以我的查看顺序有限 - 但是我可以看到元素离开队列的顺序,它显然不遵循路径我希望它.

建议？

我有一种情况,当一个msg失败,我想使用python boto包重放那个具有最高优先级的msg,所以他将被带走.如果我没错,SQS队列不支持优先级队列,所以我想实现一些简单的东西.

重要提示:当msg失败时,我不再拥有消息对象,我只保留receipt_handle,这样我就可以删除消息(如果有超过x次重试)/更改超时可见性,以便将他推回队列.

谢谢!

我正在学习数据结构课程并且对于被认为是ADT(抽象数据类型)和什么不是(如果它不是ADT那么它必须是实现？)有点困惑.

具体来说,我在谈论堆.

我在维基百科中读到"堆是一种专门的基于树的数据结构",这是否意味着它是一个ADT？如果是这样,那么我无法理解以下这一行,也来自维基百科"堆是一种称为优先级队列的抽象数据类型的最高效实现".

我的意思是,Heap可以是ADT还是其他ADT的实现(在这种情况下是优先级队列的实现？我理解ADT的概念并且在Binary Heap的上下文中我理解它可以使用数组实现arr[i]是的父arr[2i]和arr[2i + 1] 我只是混淆一个堆是否可以在一方面使用阵列实现的ADT和在另一方面一个数据结构实现其他ADT.

想得到一些澄清.

例如，给定一个 Integer 列表List<Integer> list = Arrays.asList(5,4,5,2,2)，如何maxHeap从该列表中获取O(n)时间复杂度的 a ？

天真的方法：

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (Integer i : list) {
    maxHeap.offer(i);
}

然而，时间复杂度为O(nlogn)。

我们可以使用以下构造函数来触发heapify方法：

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(list);

时间复杂度为O(n). 然而，它迫使我使用自然顺序，即minHeap。

我的问题：

如何通过使用自定义比较器堆化集合来构造 PriorityQueue？

参考： PriorityQueue 的 Java 文档

PS：@user207421
Heapify算法可以及时将任何未排序的数组转换为堆O(n)，而不是O(nlogn)。关于heapify的文章有很多，也在CLRS的Introduction to Algorithms Page 159中，从任何未排序的数组构建堆是O(n)。而且堆也不是排序数组。它是一个完整的树，具有堆属性，可以用数组进行编码。