标签: priority-queue

您将如何使用C中的链接列表实现优先级队列？

典型的链表包括head指向指向另一个元素的元素,该元素最终以NULL链接列表的尾部结尾.例:

(Linked List | Head) ----> (Element | Next) ----> (Element | Next) ----> Null

在基本场景中,通过使用先进先出(添加到列表末尾,从列表前面删除)FIFO方法将新元素添加到列表中.

但是,在我的情况下,必须考虑优先级值.更具体地说,每个元素可以被赋予1,2或3的优先级.具有最高优先级的元素被添加到列表的前面,而具有较低优先级的元素被添加到后面.插入列表会保持每个优先级的FIFO顺序.

因此,如果要一次将一个元素排入队列:

a 3, b 1, c 2, d 3, e 2

输出应该是:( a 3, d 3, c 2, e 2, b 1按优先级排序,以及添加的顺序,而不是标准的先入先出方法,忽略优先级).

这是我所拥有的,但它没有优先权.您将如何实施优先级队列？

http://codepad.org/BMeuSgNBxd

一种方法是使用排序/优先级算法.除了算法之外,对我来说,一些主要的未知数/混淆是如何以及在何处存储优先级,它是否在实际元素中,例如:

(Linked List | Head)---->(a | 1 | Next)---->(b | 2 | Next)----> Null

要么

  q_enqueue(&q, "a", "1");
  q_enqueue(&q, "b", "2");

在使用指针创建排序算法时,我将如何比较优先级.

我希望增加或降低项目的优先级PriorityQueue:例如,我可能正在下载一长串图像,并突然希望第三十个具有最高优先级.

据我了解,poll()总是返回具有最低值的队列对象(由比较器确定).如果我可以降低一个项的值已经在队列中(例如,如果这个值由确定int在所述对象和我降低int值在一些其它功能),将它首先通过返回poll(),或者是其允许分选poll()至在插入时完成此操作(例如,通过将新队列元素向下列入列表直到它们达到"自然"深度)？

如果在a上完成PriorityBlockingQueue,是否会导致并发问题？

我正在尝试将优先级队列定义为二叉树,但不断收到语法错误

    type 'a priority_queue = PriorityQueue of (Leaf | Node of 'a priority_queue * ('a*int) * 'a priority_queue)

当我这样做时,我也会收到错误

type 'a priority_queue = (PriorityQueue of Leaf) | (PriorityQueue of Node of 'a priority_queue * ('a*int) * 'a priority_queue) 

我该如何定义？

我试图使用优先级队列,但remove()不起作用:我的代码:

PriorityQueue<OwnClass> pq=new PriorityQueue<OwnClass>();
OwnClass a=new OwnClass(1);
OwnClass b=new OwnClass(2);
OwnClass c=new OwnClass(3);
pq.add(a);
pq.add(b);
pq.add(c);
System.out.println("head:"+pq.peek());
pq.remove(new OwnClass(1));
System.out.println(pq.peek());

和类实现:

class OwnClass implements Comparable{

    int x;

    public OwnClass(int x){
        this.x=x;
    }

    public int compareTo(Object arg0) {

        OwnClass a=(OwnClass) arg0;
        if(a.x>this.x)
            return -1;
        if(a.x<x)
            return 1;
        return 0;
    }

    public String toString(){
        return ""+x;        
    }
}

我认为输出最终输出应该是2,因为我删除了添加的'1'.compareTo()应该由优先级队列remove()使用,但他的情况似乎并非如此.我做错了什么？我知道pq.remove(a)会起作用,但我的代码也应该有用

出于某种原因,当我添加到优先级队列时,它不会完全按字母顺序排序我的字符串,我不明白为什么.

这是添加到PriorityBlockingQueue的代码:

String toAdd = String.format("%s/%s", directory, s);
outputData.add(toAdd);

但我没有完全排序输出(只有前几行,但你可以看到它没有排序):

../StartingTree/files/abknl/apfmpohgyh/a.class
../StartingTree/files/abknl/apfmpohgyh/a.java
../StartingTree/files/abknl/aqybc/aeph.java
../StartingTree/files/abknl/apfmpohgyh/bnjuxxdi.class
../StartingTree/files/abknl/bbxudleuf/jlffhq/y/xwjj/dyetqhsch/bpg.class
../StartingTree/files/abknl/bbxudleuf/mxb/fe/ndmg/axapxuco.html
../StartingTree/files/abknl/aqybc/atyuojdu.txt

这是预期输出文件的排序输出的真实(第一部分):

../StartingTree/files/abknl/apfmpohgyh/a.class
../StartingTree/files/abknl/apfmpohgyh/a.java
../StartingTree/files/abknl/apfmpohgyh/bnjuxxdi.class
../StartingTree/files/abknl/apfmpohgyh/bnjuxxdi.java
../StartingTree/files/abknl/apfmpohgyh/bsqsq.class
../StartingTree/files/abknl/apfmpohgyh/bsqsq.java
../StartingTree/files/abknl/apfmpohgyh/ds.class
../StartingTree/files/abknl/apfmpohgyh/ds.java

我编写了以下代码来接受许多输入,然后按特定顺序输出它们.

#DEFINE cases 100     

struct job
{
int w;
};

class compjob
{
public:
       bool operator()( job j1,job j2)
       {
       if(j2.w>j1.w)
       return true;

       return false;
       }
};

int main()
{
priority_queue< job, vector<job>, compjob > jobs;

int weight;



for(int i=1;i<=cases;i++)
{
cin>>weight;
job job1;
job1.w=weight;

jobs.push(job1);
} //for loop ends here


for(int i=1;i<=cases;i++)
{
job job1= jobs.pop(); ////////////ERROR!!!!!/////////
cout<<job1.w<<endl;
}

return 0;;
}

但是当我编译代码时,在上面标记的行上显示编译错误:

Invalid conversion from 'void' to non scalar 'job'.

我认为我没有正确地声明作业priority_queue.另外,请解释声明中第二个参数的意义(即矢量,我真的不知道它的用途)

我需要在Haskell中使用堆树实现优先级队列,例如:

给出一个清单: [3,2,7,8,4,1,9]

3 is the  main root
2 is its left leaf
7 is its right leaf

8 is the left leaf of 2
4 is the right leaf of  2

1 is the left leaf of 7
9 is the right leaf of 7

如果我想堆树,那就像这样:

7 > 3 so we exchange them
8 > 2 we exchange them
8 > 7 we exchange them
9 > 3 we exchange them
9 > 8 we exchange them

我们以这样的列表结束: [9,7,8,2,4,1,3] …

我有一个priority queue班级,像这样:

    class Foo
    {
    public:
        //public methods...
    private:
        std::priority_queue<Obj, std::vector<Obj>, object_less> foo_queue;

        //private methods and members...
    }

我一直在使用该emplace()方法在我的内部插入对象priority_queue,如下所示:

void Foo::add( ... ) {
    foo_queue.emplace(var1, var2);
}

这将调用构造函数Obj(var1,var2)并将其插入到priority queue.

但现在,我需要std::vector<Obj>从外面访问.从我的Obj对象.

类似于创建一个Foo object和更改成员的东西,它位于以下对象内priority_queue:

Foo myFoo; // <-- this is where the priority_queue is!

Obj myObj(1); //Creating an object that has some member with value '1'

myFoo.add(myObj); //This will add the object to the …

我一直在尝试创建一个优先级队列,其中每个元素都是一对存储指向unsigned int和unsigned int的指针.问题是每当我向优先级队列添加一对时,先前添加的对指向的元素将其值切换为0.

这是代码

#include <iostream>
#include <vector>
#include <utility>
#include <queue>

typedef unsigned int ui;
typedef std::pair<ui*, ui> Ppuiui;
typedef std::priority_queue<Ppuiui> Queue;

void showPQ(Queue Q)
{
    while(!Q.empty())
    {
        std::cout << *(Q.top().first) << " -> " << Q.top().second << std::endl;
        Q.pop();
    }
    std::cout << std::endl;
}

int main(void)
{
    std::vector<ui> distance;
    Queue Q;

    //Adding elements to the priority queue while showing them
    distance.push_back(2500);
    Q.push(Ppuiui(&(distance[0]), 0));
    showPQ(Q);

    distance.push_back(1000);
    Q.push(Ppuiui(&(distance[1]), 1));
    showPQ(Q); …

PriorityQueue 在Java 1.5中添加了

new PriorityQueue()在Android中启用,但是

  new PriorityQueue(new Comparator() {
        @Override
        public int compare(Object o1, Object o2) {
            return 0;
        }
    });

需要API 24.为什么？