标签: priority-queue

它甚至不执行推送操作。它不调用推送函数，只是构造函数调用和分段错误。为什么会这样？

class Heap {
    vector<int> v;

     void Heapify(int x) {
        int mi = x;
        int l = 2 * x;
        int r = 2 * x + 1;

        if (v[mi] > v[l] && l < v.size()) {
            mi = l;


        }
        if (v[mi] > v[r] && r < v.size()) {
            mi = r;
        }

        if (mi != x) {
            swap(v[mi], v[x]);
            Heapify(mi);
        }
                       }
public:
    Heap() {

        v[0] = -1;
    }
    void push(int x) {

        v.push_back(x);
        int i = v.size()-1; …

std::greater当你有课std::pair的时候有用吗int？

我正在尝试创建一个成对的优先级队列，按第一个元素排序：

std::priority_queue<std::pair<double, classA>, std::vector<std::pair<double, classA>>, std::greater<std::pair<double, classA>>> priorityQueue

但我收到一条错误消息

与“运算符<”不匹配

它暗示了 的第二个元素std::pair，它是类类型。

应用于std::greater第一个和第二个元素std::pair？

我在 Java 中使用 PriorityQueue。

我有一个具有这种结构的对象：

public class CostObject {

  String value;
  double cost;

  public CostObject(String val, double cst) {
    value = val;
    cost = cst;
  }
}

优先级是从最便宜到最贵的成本：

PriorityQueue<CostObject> queue = new PriorityQueue<>(1, new Comparator<CostObject> () {

    @Override
    public int compare(CostObject co1, CostObject co2) {
            return (co1.cost > co2.cost) ? 1 : -1;
    }

});

我使用 add 在队列中包含对象。

CostObject co = new CostObject("test", cost);
queue.add(co);

它适用于队列中的每个元素，但我添加的最后一个元素始终位于底部位置。

我究竟做错了什么？

我有一个使用 PriorityQueue 的简单代码，我希望整数以降序存储。

PriorityQueue<Integer> jumps = new PriorityQueue<>(20,Collections.reverseOrder());
jumps.add(8);
jumps.add(5);
jumps.add(15);
jumps.add(2);
jumps.add(16);
System.out.println(jumps.toString());

这打印

[16, 15, 8, 2, 5]

虽然我会期待

[16, 15, 8, 5, 2]

我在这里做错了什么？

我正在初始化一个存储 XY 坐标的优先级队列，根据距原点的欧几里得距离确定优先级。我创建了一个自定义Comparer，使其作为最大堆运行：

PriorityQueue<int[], double> maxHeap = new PriorityQueue<int[], double>(Comparer<double>.Create((x, y) => x.CompareTo(y)));

这非常有效，除了有时我希望能够使用Peek(). 我可以获取元素的值，即具有 type 的点int[]，但无法获取优先级。我没有看到任何可以让我访问的东西TPriority。以此用例为例，这是堆的常见用法，用于获取集合中的顶部/底部 K 个元素：

for (int i = k; i < points.Length; i++)
{
    double euclidianDistance = EuclidianDistance(points[i]);
    if (euclidianDistance < EuclidianDistance(maxHeap.Peek()))
    {
        maxHeap.Dequeue();
        maxHeap.Enqueue(points[i], euclidianDistance);
    }
}

您将看到我必须再次计算堆顶部元素的欧几里德距离。Visual Studio 向我展示了这一点，尽管我似乎无法访问引用优先级的 double 类型的第二个属性。

public class PriorityQueue<T> : IPriorityQueue<T> 
                            where T : IComparable

所以,我已经使用上面的Header创建了一个优先级队列类,我试图将它与另一个类一起使用.

        private static PriorityQueue<Order> PQ;

看起来这应该完全正常,但我收到了这个错误.

我namespace.Order不能T在泛型方法中用作类型参数namespace.PriorityQueue<T>.有没有隐式转换从namespace.Order到System.IComparable

我无法辨别出这是告诉我要做什么的.这是否意味着我的IComparable实现不足以达到此目的,还是我正在使用某种错误的语法？

我对java.util.PriorityQueue和我自己的Comparator的这个小例子感到非常困惑：

在这段代码中，我在队列中得到了错误的顺序。结果是：5,8,7而不是5,7,8 我有什么问题Comparator<Vertex>吗？谢谢您的帮助。

public class Test {

public static void main(String[] args) {
    PriorityQueue<Vertex> priorityQueue = new PriorityQueue<Vertex>(new Comparator() {
        @Override
        public int compare(Object o1, Object o2) {
            Vertex u = (Vertex) o1;
            Vertex v = (Vertex) o2;
            return Integer.compare(new Integer(u.distance), new Integer(v.distance));
        }
    });

    Vertex vertex1 = new Vertex(1);
    Vertex vertex2 = new Vertex(2);
    Vertex vertex3 = new Vertex(3);
    Vertex vertex4 = new Vertex(4);

    vertex1.distance = 8;
    vertex2.distance = 5;
    vertex3.distance = 7;


    priorityQueue.add(vertex1); …

谁能解释一下这个声明的含义：

typedef pair<long long, int> PII;
priority_queue<PII, vector<PII>, greater<PII> > Q;

是否将其视为一对long long和int或其他的优先级队列？请有人也解释一下greater<PII>这里是什么？

我需要计算中位数.我被告知,最好的方法是在这个特定的应用程序中使用优先级队列.我不知道如何继续.我真的很感激任何帮助.

考虑以下代码：

import java.util.PriorityQueue;

public class Test {

    public static void main(String argv[]) {
        PriorityQueue<A> queue = new PriorityQueue<>();
        System.out.println("Size of queue is " + queue.size()); // prints 0
        try {
            queue.add(new A());
        } catch (ClassCastException ignored) { }
        System.out.println("Size of queue is " + queue.size()); // prints 1
    }

} 
class A { } // non-comparable object

在此代码中，一个明确不可比较的对象被添加到PriorityQueue. 正如PriorityQueue.addJavadoc 所预期的那样，此代码会抛出 a ClassCastException，因为该对象不可比较。

然而，尽管抛出了异常，但队列的大小似乎仍然增加了。

我原本期望两个打印语句都输出 0，但第二个打印语句实际上输出 1，就像一个对象已添加到队列中一样。

这里发生了什么？

PriorityQueue pq = new PriorityQueue<>(); 假设priorityQueue pq 的大小为N，pq.remove() 的时间复杂度是多少？

是 O(log N) 还是 O(N)？

PriorityQueue<Pair<Integer, Integer>> p = new PriorityQueue<>((a,b)->a.getValue()-b.getValue());

这就是优先级队列的定义方式，其中您可以看到元素是根据键值对中的值而不是键进行排序的。现在我想删除一个特定的元素（不在队列顶部），使用键作为搜索因子。假设队列有元素 ->

p.add(new Pair<>(2,1));
p.add(new Pair<>(3,4));
p.add(new Pair<>(1,5);

我想使用键 (3) 删除元素 (3,4)；

删除后的预期输出应该是 -> [[2,1], [1,5]]

我需要使用 STL 向量为优先级队列编写代码

我被分配了使用向量实现优先级队列的任务，之前我使用列表实现了一个队列，这非常简单，因为列表为我提供了我需要的所有功能。除非我遗漏了优先级队列所没有的东西？

cplusplus.com 上对 Priority Queue 的参考说明：在底层容器（向量）上调用 push_back 和对 push_heap 调用一次（我假设是算法），我不确定如何实现 push_heap 和 pop_heap 或者我是否需要根本。

作业特别要求向量

我正在寻找一个很好的实现/解释。

到目前为止，这是 mo 代码：

.cpp

#include"PriorityQueue.h"
#include <algorithm>

PriorityQueue::PriorityQueue(){

}
void PriorityQueue::push(double val){
    s.push_back(val);

}
void PriorityQueue::pop(){


}
double PriorityQueue::front() const{
    return s.front();
}
double PriorityQueue::back() const{
    return s.back();
}

。H

#ifndef PRIORITYQUEUE_H
#define PRIORITYQUEUE_H
#include <vector>
using std::vector;
class PriorityQueue{
public:
    PriorityQueue();
    void push(double val);
    void pop();
    double front() const;
    double back() const;
private:
    vector<double> s;
};
#endif // !PRIORITYQUEUE_H

如果我需要编写代码来跟踪顶部和底部索引，我可能会缺少基本功能，我只是有点卡住了，没有时间浪费尝试不同解决方案的负载。