标签: priority-queue

F#库是否包含优先级队列？有人可以指点我在F#中实现优先级队列吗？

我创建了一个二进制堆,它代表一个优先级队列.它只是经典的众所周知的算法.此堆计划不同事件的时间顺序(排序键是时间).

它支持2种操作:插入和删除.堆的每个节点的密钥大于或等于其每个子节点.但是,使用相同的键添加事件不会保留它们的添加顺序,因为每次调用Remove或Insert后,堆启动和堆降过程都会破坏顺序.

我的问题是:在经典算法中应该改变什么以保持具有相同优先级的节点的顺序？

使用Scala 2.9实现一种Dijkstra算法(伪代码)

val queue = new PriorityQueue
queue.insert(...)
while (!queue.isEmpty) {
  val u = queue.extractMin
  queue.foreach { v =>
    if (condition(u, v))
      queue.decreaseKey(v, newPriority)
  }
}

我想改变Scala中项目的优先级collection.mutable.PriorityQueue.

因此试图

• 除去项目
• 改变优先权
• 重新插入队列.

但是我找不到一种方法来更新优先级或删除特定项目(不一定是头元素),就像从优先级队列java.util.PriorityQueue#remove(Object)中 删除项目一样.

• 如何完成此任务scala.collection.mutable.PriorityQueue 或者我必须使用java.util.PriorityQueue？

• 有没有人知道这种方法是否缺乏设计,并且建议在更改某些项目的优先级后重建队列(可能需要查看有关优先级队列与动态项目优先级的讨论)？

我试图插入整数PriorityQueue,我知道:

如果在PriorityQueue构造a时未指定比较器,则使用存储在队列中的数据类型的默认比较器.默认比较器将按升序对队列进行排序

但是,我得到的输出不是按排序顺序.运行以下代码后的输出是:[2, 4, 8, 6]

public static void main(String args[]) {
    PriorityQueue<Integer> q = new PriorityQueue<Integer>(10);
    q.offer(4);
    q.offer(2);
    q.offer(8);
    q.offer(6);

    System.out.print(q);
}

有人可以解释一下原因吗？

我在使用优先级队列来识别它应该排序的参数时遇到了很多麻烦.我在我的自定义类中重载了less运算符但它似乎没有使用它.这是相关的代码:

Node.h

class Node
{   
public:
    Node(...);
    ~Node();
    bool operator<(Node &aNode);
...
}

Node.cpp

#include "Node.h"
bool Node::operator<(Node &aNode)
{
    return (this->getTotalCost() < aNode.getTotalCost());
}

getTotalCost()返回一个int

main.cpp中

priority_queue<Node*, vector<Node*>,less<vector<Node*>::value_type> > nodesToCheck;

我错过了什么和/或做错了什么？

我正在使用优先级队列作为具有一个额外要求的调度程序.我需要能够取消预定的项目.这相当于从优先级队列的中间删除项目.

我无法使用std::priority_queue除了top之外的任何元素的访问受到保护.

我正在尝试使用algorithm堆函数.但我仍然错过了我需要的那件作品.当我从堆中间删除一个元素时,我希望它能够有效地重建它自己.C++提供了这些堆函数:

• std::make_heap O(3N)
• std::push_heap O(LG(n))的
• std::pop_heap O(2 lg(n))

我想要一个像std::repair_heap大O < 3n这样的新功能.我将它提供了取消项目所在的洞的位置,它将适当地调整堆.

不提供std::repair_heap功能似乎是一个巨大的疏忽.我错过了一些明显的东西吗

是否有提供符合stl标准的库std::repair_heap？

是否有更好的数据结构来建模调度程序？

注意:由于某些原因,
我没有使用std::map.

• 堆具有恒定的内存开销.
• 堆具有令人敬畏的缓存局部性.

我有一个指向a的优先级队列struct city.我修改优先级队列外的这些指针指向的对象,并希望告诉优先级队列根据新值"重新排序"自己.

我该怎么办？

例:

#include <iostream>
#include <queue>

using namespace std;

struct city {
    int data;
    city *previous;
};

struct Compare {
    bool operator() ( city *lhs, city *rhs )
    {
        return ( ( lhs -> data ) >= ( rhs -> data ) );
    }
};

typedef priority_queue< city *, vector< city * >, Compare > pqueue;

int main()
{
    pqueue cities;

    city *city1 = new city;
    city1 -> data = 5;
    city1 -> previous = NULL; …

有人曾经实施过Brodal队列吗？

是否值得实施或具有像Fibonacci Heap这样的高运行时间常数？

我认为add()应该忽略重复,但我的输出有重复.我怎么不存储重复？

我还想知道优先级队列如何检查两个元素是否重复.我猜它正在使用比较器等于,但我只想确定.

谢谢

我尝试在不使用优先级队列(Heap)的情况下在循环加权图上使用Djikstra算法,并且它有效.

然后我搜索谷歌"为什么我们需要一个优先级队列来实现这个？" 作为搜索的结果,我浏览了维基百科,在那里我了解到原始实现不使用优先级队列并在O(| V | 2)中运行,即V平方时间.

现在,如果我们只删除优先级队列并使用正常队列,则运行时间是线性的,即O(V + E).

请有人建议那么为什么我们需要优先队列？