标签: priority-queue

我有一个PriorityBlockingQueue包含元素列表的元素。我已经实现了 Comparable 接口并覆盖了compareTo()以定义哪个元素小于，等于 o 大于其他元素。

所以我想知道优先队列是如何工作的，也就是说，它什么时候对它的元素进行排序？自动处理队列中的任何事件（添加、删除、修改）？

谁能向我解释优先队列是如何工作的？我不清楚。

我有这个案例类：

case class Offer(id: Int, amount: Int, interestRate: Double) extends Ordered[Offer] {

  def compare(that: Offer) = interestRate.compareTo(that.interestRate)
}

如您所见，我定义了基于Offer.interestRate. 我希望订单增加。

我创建了这些优惠：

Offer(1, 5, 4.0)
Offer(2, 5, 0.5)
Offer(3, 5, 1.5)

并将它们添加到优先级队列中：

val currentOffers: mutable.PriorityQueue[Offer] = mutable.PriorityQueue.empty[Offer]

问题是，当我这样做时，currentOffers.dequeue()我得到Offer(1, 5, 4.0).

相反，我想得到：

Offer(2, 5, 0.5)

我需要改变什么？

我是 python 的新手，刚刚在尝试遍历队列时发现了一个奇怪的错误。

这是一个代码片段：

frontier = q.PriorityQueue()

    for goal in goals:
        portals = findPortals(maze)
        comb_value = heuristic(startX, startY, goal[0], goal[1])
        frontier.put_nowait((comb_value, heuristic(startX, startY, goal[0], goal[1]), 0, startX, startY, startX, startY))

        for portal in portals:
            heur = portalHeuristic(maze, startX, startY, goal[0], goal[1])
            frontier.put_nowait((heur, heur, 0, startX, startY, startX, startY))

    for elem in list(frontier):
        print(elem)

当试图打印出它说的元素时TypeError: 'PriorityQueue' object is not iterable。我能以某种方式解决这个问题吗？我试图在这里找到一些解决方案，但我没有真正找到我理解的任何东西......

我需要计算每秒获得的数字流的第 90 个百分位数。它可能高达每秒数百万个数字，但第 90 个百分位数只需要近似，不一定准确。优先队列/最大堆是执行此操作的最佳方法还是其他方法？如果是这样，我最终将如何估算该值？

我正在尝试queue.PriorityQueue在 Python 3(.6) 中使用。

我想存储具有给定优先级的对象。但是如果两个对象具有相同的优先级，我也不介意PriorityQueue.get返回。换句话说，我的对象不能以整数进行比较，允许它们是没有意义的，我只关心优先级。

在Python 3.7 的文档中，有一个涉及dataclasses. 我引用：

如果数据元素不可比较，可以将数据包装在一个忽略数据项而只比较优先级数字的类中：

from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

唉，我使用的是 Python 3.6。在这个版本的 Python 的文档中，没有关于使用PriorityQueue优先级的评论，也不关心在我的情况下不合逻辑的“对象值”。

有没有比__le__在我的自定义类上定义和其他比较方法更好的方法？我发现这个解决方案特别丑陋和违反直觉，但这可能是我。

我有一个里面有 PriorityQueue 字段的类：

public class MyClass<T>{
    Queue<T> queue = new PriorityQueue<>();

我想以某种方式从 MyClass 获取一个流并使用 foreach 并希望序列按照我的 PriorityQueue 的优先级顺序运行。最简单的方法是覆盖 stream() 方法：

@Override
public Stream stream() {
    return queue.stream();
}

但这不会按优先级顺序公开队列元素。所以问题是：如何让 foreach 流方法表现得像：

    while(!queue.isEmpty()) 
        queue.poll();

我有一个类Person，它有两个属性 Name( String) 和 Weight( Integer)。

我想根据它们的权重以降序将元素存储在 PriorityQueue 中，即元素在队列中的顶部权重越高。

到目前为止我已经尝试过这个：

PriorityQueue<Person> personPriorityQueue = new PriorityQueue<Person>((a,b)-> Integer.compare(a.getWeight(), b.getWeight()));
        personPriorityQueue.add(new Person(40,"N1"));
        personPriorityQueue.add(new Person(60,"N2"));
        personPriorityQueue.add(new Person(50,"N3"));

        personPriorityQueue.forEach(s-> System.out.println(s.getName()));

我得到的输出是：

N1
N2
N3

我应该得到：

N2
N3
N1

我过去写过几乎类似的代码并且它有效（我记得很模糊）。似乎比较器在这里不起作用？有什么线索吗？

#include<iostream>
#include<vector>
#include<queue>
#include<iterator>
#include<algorithm>
using namespace std;

    typedef pair<vector<int>::iterator,vector<int>::iterator> PR;
    struct CompareFn{
        bool operator()(const PR& a, const PR& b){
            //cout<<"a and b first: "<<*(a.first)<<" "<< *(b.first)<<endl;
            return *a.first > *b.first;
        }
    };

vector<int> mergeKSortedArrays(vector<vector<int>> &A) {  
vector<int> result;
    
    priority_queue<PR, vector<PR>, CompareFn> PQ;
    for(auto e:A){  
        if(e.size()>0) PQ.push({e.begin(),e.end()});
    }

    while(PQ.size()>0) {
        PR tmp = PQ.top(); PQ.pop();
        auto cur=tmp.first;
        auto lst=tmp.second;
        result.emplace_back (*cur);
        if((++cur)!=lst) PQ.push({cur,lst});
    }
return result;
}


int main() { 
vector<vector<int>> v= {{2,3,8,10},{1,4,12},{4,5,8}};
 vector<int> result = mergeKSortedArrays(v);
 copy(result.begin(),result.end(), ostream_iterator<int>(cout," …

我正在尝试将 C++ STL 优先级队列与自定义类型和比较器一起使用，但无论我怎么说，我都会收到错误消息。

有谁知道可能是什么问题？我正在尝试从文档中复制语法，但没有任何效果...

自定义类型是指向 LeetCode 中使用的 ListNode 类的指针：

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

在我的班级中，我有一个静态比较函数：

static bool compare(ListNode* n1, ListNode* n2) {
    return n1->val < n2->val;
}

我正在尝试像这样初始化优先级队列：

priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> pq(compare);

但我不断收到错误，说：

In file included from prog_joined.cpp:1:
In file included from ./precompiled/headers.h:55:
In …

在std::priority_queue默认情况下使用std::vector<int>和std::less比较。默认情况下，priority_queue 是最大堆。

top()的文档指出：

所述顶部元件是比较在较高的元件priority_queue，和被从容器中取出时，下一个priority_queue::top将被调用。

这个成员函数有效地调用front了底层容器对象的成员。

因此，默认构造priority_queue的整数构造如下：

auto maxheap = priority_queue<int>();
maxHeap.push(1);
maxHeap.push(3);
cout << maxHeap.top(); // outputs 3

然而，回到对 的描述top()，文档指出，实际上，front底层容器对象上的成员被调用。如果我创建一个向量并使用排序std::less来模拟我们的 maxHeap 的底层容器：

auto vec = vector<int>{3, 1};
sort(vec.begin(), vec.end(), less<int>()); // {1, 3}
cout << vec.front(); // outputs 1

因为std::less按升序排序，调用vec.front()最终返回最小值。

我对priority_queue::top()文档的默认行为和内容的理解存在一些脱节。有人可以向我解释一下吗？