标签: priority-queue

似乎它们都让你检索最小值,这是我对Prim算法所需要的,并强制我删除并重新插入一个键来更新它的值.使用一个优于另一个是否有任何优势,不仅仅是这个例子,但一般来说？

在我的程序中,我需要从不在顶部的优先级队列中删除一个元素.可以这样做吗？如果没有,请建议一种方法,除了创建自己的堆.

我有一个我想用来创建堆的向量.我不确定是否应该使用C++ make_heap函数或将我的向量放在优先级队列中？在性能方面哪个更好？我何时应该使用一个与另一个？

remove()Java中Priority Queue类的函数的复杂性(大哦)是多少？我无法在任何地方找到任何记录,我认为它是O(n),考虑到你必须在删除之前找到该元素然后重新洗牌.但我看到其他人不同意并认为这是O(登录).有任何想法吗？

似乎优先级队列只是具有正常队列操作的堆,如insert,delete,top等.这是解释优先级队列的正确方法吗？我知道您可以以不同的方式构建优先级队列但是如果我要从堆构建优先级队列,则需要创建优先级队列类并提供构建堆和队列操作的说明,或者是否真的不需要构建班级？

我的意思是如果我有一个函数来构建一个堆和函数来执行像insert,delete这样的操作,我是否需要将所有这些函数放在一个类中,或者我可以通过调用它们来使用它们main.

我想我的问题是,拥有一组函数是否等同于将它们存储在某个类中并通过类或仅使用函数本身来使用它们.

我下面是优先级队列实现的所有方法.这足以称之为实现,还是需要将其置于指定的优先级队列类中？

#ifndef MAX_PRIORITYQ_H
#define MAX_PRIORITYQ_H
#include <iostream>
#include <deque>
#include "print.h"
#include "random.h"

int parent(int i)
{
    return (i - 1) / 2;
}

int left(int i)
{
    if(i == 0)
        return 1;
    else
        return 2*i;
}

int right(int i)
{
    if(i == 0)
        return 2;
    else
        return 2*i + 1;
}

void max_heapify(std::deque<int> &A, int i, int heapsize)
{
    int largest;
    int l = left(i);
    int r = right(i);
    if(l <= heapsize && A[l] …

Ruby的标准库是否有优先级队列实现？

我有一个优先级队列,我在其中添加一个Node对象,其中节点应按其包含的值排序.由于某种原因,优先级队列不会对添加的节点进行排序.如果有人可以看到这个问题或有任何指导,我很感激.这是一个简短的例子:

PriorityQueue<Node> PQ = new PriorityQueue<Node>();
        //for each entry create a node and add it to the PriorityQueue
        for(Entry<Character,Integer> entry : entries){
            PQ.add(new Node(entry.getKey(),entry.getValue(), true));
        }

这是节点的compareTo方法:

@Override
public int compareTo(Node n) {
  if(n.frequency.intValue() > this.frequency.intValue()) return  -1;
  else if(n.frequency.intValue() == this.frequency.intValue()) return 0;
  else return 1;
}

我经常搜索,但找不到解决问题的方法.

我有自己的类,BaseTask使用a ThreadPoolExecutor来处理任务.
如果我不想要优先级(即使用a PriorityBlockingQueue),这可以正常工作,但当我尝试使用ClassCastException我得到的ThreadPoolExecutor因为FutureTask将我的任务包装到一个FutureTask对象中.
这显然是可以的,因为Comparable它没有实现newTaskFor(),但我将如何继续解决优先级问题？
我读过您可以覆盖ThreadPoolExecutor在BaseTask,但我似乎无法在所有发现这个方法...？

我们欢迎所有的建议!

一些代码可以帮助:

在我的BaseFutureTask班上,我有

private static final BlockingQueue<Runnable> sWorkQueue = new PriorityBlockingQueue<Runnable>();

private static final ThreadFactory sThreadFactory = new ThreadFactory() {
    private final AtomicInteger mCount = new AtomicInteger(1);

    public Thread newThread(Runnable r) {
        return new Thread(r, "AsyncTask #" + mCount.getAndIncrement());
    }
};

private static final BaseThreadPoolExecutor sExecutor = new BaseThreadPoolExecutor(
    1, Integer.MAX_VALUE, …

我正在尝试使用优先级队列来实现Dijkstra的算法来寻找最短路径.在算法的每个步骤中,我删除距离优先级队列最短距离的顶点,然后更新优先级队列中每个邻居的距离.现在我读到Java中的优先级队列在编辑其中的元素(确定排序的元素)时不会重新排序,所以我试图通过插入和删除虚拟顶点来强制它重新排序.但这似乎并没有起作用,而且我一直试图解决这个问题.

这是顶点对象和比较器的代码

class vertex {
    int v, d;
    public vertex(int num, int dis) {
        v=num;
        d=dis;
    }
}

class VertexComparator implements Comparator {
    public int compare (Object a, Object b) {
        vertex v1 = (vertex)a;
        vertex v2 = (vertex)b;
        return v1.d-v2.d;
    }
 }

这是我运行算法的地方:

    int[] distances=new int[p];
    Comparator<vertex> comparator = new VertexComparator();
    PriorityQueue<vertex> queue = new PriorityQueue<vertex>(p, comparator);
    for(int i=0; i<p; i++) {
        if(i!=v) {
            distances[i]=MAX;
        }
        else {
            distances[i]=0;
        }
        queue.add(new vertex(i, distances[i]));
    }
    // run dijkstra
    for(int i=0; …

什么更快:插入优先级队列,还是追溯排序？

我正在生成一些我需要在最后排序的项目.我想知道,在复杂性方面更快的是:将它们直接插入priority_queue或类似的数据结构中,还是在结尾处使用排序算法？