标签: priority-queue

我想通过使用这样的指定值将对象添加到优先级队列

PriorityQueue<Edge> queue=new PriorityQueue<Edge>();

这是 Edge 类，我想按其权重在优先级队列中排序

public class Edge {
private int start,end;
private double weight;

public Edge(int s, int e,Double w){
    start=s;
    end=e;
    weight=w;
}

public int getStart(){
    return start;
}

public int getEnd(){
    return end;
}

public double getWeight(){
    return weight;
}

我正在尝试将项目从优先级队列中复制到ArrayList. 出于某种原因，当有三四个项目时，它会在向列表中添加两个项目后停止。如果有5项目，它会在将3项目复制到列表后停止。我究竟做错了什么？

PriorityQueue<T> queue= new PriorityQueue<T> () ; 
List<T> list = new ArrayList<T>();

 for (int i = 0 ; i< queue.size(); i++)
        {
           list.add(0, queue.poll());
        }

我正在向 PriorityQueue 添加边，但由于某种原因，它们没有按它们的值进行排序，导致以后出现错误结果。

我的边缘类看起来像这样

class Edge implements Comparable<Edge>{
int value;
String dest;
String start;

public Edge(String start, String dest, int g) {
    this.dest = dest;
    value = g;
    this.start = start;
}
@Override
public int compareTo(Edge o) {
    int temp = value - o.value;
    if (temp > 0) {
        return 1;
    }
    if (temp < 0) {
        return -1;
    }
    return 0;
}

然而，当我运行我的代码，在属于节点“Springfield，MO”的 LinkedList 上执行 addAll 到 PriorityQueue 时，边缘按错误的顺序排序，如下所示，有什么问题？

queue.addAll(list.get(node));

我试图为 Edge 制作一个特定的比较器类并将其用作 PriorityQueue 中的参数，但我仍然得到相同的结果。

我正在尝试在元组列表上实现最小堆。例如：

A=[('a',2),('b',1)]

我如何根据这些元组的第二个元素堆化 A ，以便将 A 堆化为[('b',1),('a',2)]？（我必须维护一个最小堆。）

有没有办法用 O(N) 复杂度的一些元素来初始化优先级队列？可能使用 heapify 算法。

我搜索了该问题但找不到解决方案。另外，我知道 make_heap()，但这是另一回事，与优先级队列无关。

为什么当priority_queue与单个数据类型使用，就像“诠释”，我们初始化像这样：priority_queue<int>; 但是，当它用一对初始化时，我们添加了向量类型的第二个参数priority_queue<pair<int,int>, vector<pair<int,int>>>？

另外，我注意到有几种方法可以添加指定排序的第三个参数。

方法 1 - 结构

struct myCompare {
   bool operator()(const pair<int, int>& A, const pair<int, int>& B) {
       return A.second < B.second;
   }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, myCompare> leaderBoard;

方法 2 - Lambda

auto myComp = [](const pair<int, int>& A, const pair<int, int>& B) 
              {return A.second < B.second;};

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(myComp)> leaderBoard(myComp);

我的问题

1. 为什么是第二个参数priority_queue一个vector？这是什么意思，什么时候需要指定第二个参数？
2. 在方法 2 中，为什么decltype需要这个 lambda？
3. 方法二中，为什么对象leaderBoard需要初始化(myComp)
4. 在方法2中，为什么不能直接将我的lambda指定为第三个参数？
5. A.second …

我有一个非常愚蠢的问题,我无法弄清楚.我正在尝试重载我的"PrioQueue"类中的<<运算符.我仍然是C++的新手,我几乎尝试了我在网上找到的所有例子,但没有任何作用.

PrioQueue是我制作的模板类,它的工作方式与普通的Queue类似,但是它在顶部获得的最高值.

PrioQueue<int> intq1(5);
intq1.push(1);
intq1.push(2);
intq1.push(1);
cout << intq1;

<<运算符应该用'|'写入我推送到队列的所有值 之间.像这样:

2 | 1 | 1 |

这是我的重载运算符<<方法.

friend std::ostream& operator<<(std::ostream& out, PrioQueue q){
    while(!q.empty()){
        out.write(q.pop()); //This method pops off the top value and returns it
    }
    return out;

}

我希望这是足够的信息,但如果没有.这是我的完整代码:

#include "stdafx.h"
#include <iostream>
#include <ostream>
using namespace std;

template <typename Type>
class PrioQueue
{
private:
Type *bottom_;
Type *top_;
int size_;
public:
PrioQueue(Type size){
    bottom_ = new Type[size];
    top_ = bottom_;
    size_ = size;
}

friend PrioQueue …

我有一个User实现Comparable 的类.在我添加用户列表后,PriorityQueue<User>他们应该优先考虑scores,但由于某种原因他们没有.你可以帮我弄清楚为什么用户没有在我的分类Queue？

更新:

我通过轮询元素访问队列.prioritisedUsers.poll()它总是带有顺序尊重的随机分数.

PriorityQueue<User> prioritisedUsers = userPriorityStrategy.computeUserPriority(users);

while(!prioritisedUsers.isEmpty()){
    System.out.println(prioritisedUsers.poll().getPriorityScore());
}

OUTPUT:

0.35036433736768735
0.6619121139678329
0.09520067929838127
0.4013591573863
0.6704568389588227
0.5989900926939181
0.7320779721160738

谢谢你的帮助!

public class User implements Comparable<User>{

    private long id;
    private String fistName;
    private String lastName;
    private double priorityScore;

    public User (long id, String firstName, String lastName){
        this.id = id;
        this.fistName = firstName;
        this.lastName = lastName;
    }

    public double getPriorityScore(){
        return this.priorityScore;
    }

    public void setPriorityScore(double priorityScore){
        this.priorityScore = priorityScore;
    }

    public …

我知道我可以做priority_queue < P, vector<P>, Compare > queue;,哪里Compare是仿函数.但是,由于默认比较器是less<P>,并且它是相同的<,为什么当我执行以下操作时它不起作用:

typedef pair<int, int> P;

bool operator<(const P& a, const P& b){   
    return (a.second < b.second);                                    
} 

int main(int argc, char const *argv[]){
    int vec[] = {3, 6, 7, 8, 1, 2}; // just for testing
    priority_queue <P> queue;
    for(int i = 0; i < 6; ++i){
        queue.push(make_pair(i, vec[i]));   
    }
    cout << queue.top().second << endl; // returns 2
    return 0;
}

我知道std::priority_queue该类实现了最小堆。有没有办法将其用作最大堆？还是有替代的Maxheap结构？我知道我可以std::make_heap()在std::vectorlambda 上使用该函数来创建自己的Maxheap，但是随后使用诸如std::pop_heap()怪异的函数，并且我认为它们不易于使用。应该有一种更简单的方法，就像我认为的min_heap（priority queue）。