标签: priority-queue

我需要一个始终包含n迄今为止插入的最大项目的数据结构(没有特定的顺序).

所以,如果n是3,我们可以进行以下会话,其中插入一些数字并且容器的内容发生变化:

[]  // now insert 1
[1] // now insert 0
[1,0] // now insert 4
[1,0,4] // now insert 3
[1,4,3] // now insert 0
[1,4,3] // now insert 3
[4,3,3]

你明白了.数据结构的名称是什么？实现这个的最佳方法是什么？或者这是在一些图书馆？

我想使用一个容器,它有一个priority_queuefor元素(委托),它使用反向比较,因此pop将删除最小的元素.因此该insert函数首先检查要插入的新元素是否大于最小元素.如果是这样,我们抛出最小的并推动新元素.

(我有一个C++实现,但问题是与语言无关.)

我想知道是否有可能在PriorityQueue中找到值的索引.只是看看它是"在线"的数字.有人知道吗？

我有兴趣实现一个优先级队列,以实现一个相对简单的高效Astar实现(我的意思是优先级队列很简单).

似乎因为Skip List提供了一个简单的O(1)extract-Min操作和一个O(Log N)的插入操作,它可能与更难实现的具有O(log N)提取的Fibonacci Heap竞争 - 最小和O(1)插入.我认为Skip-List对于具有稀疏节点的图更好,而Fibonacci堆对于具有更密集连接的节点的环境更好.

这可能会使Fibonacci Heap通常更好,但我认为Big-Oh明智的这些是相似的吗？

我正在使用PriorityBlockingQueue优先级字段.在我的测试中,我使用System#currentTime()优先级 - 计算机获得相同的优先级,以至于毫秒是相同的(或者更像是PC上的毫秒具有误差幅度).

当优先级相同时,队列就像堆栈一样,这看起来很奇怪.当元素的优先级相同时,是否有一种替代方法可以使队列像正常队列一样(即FIFO而不是LIFO行为)？

如何删除优先级队列的尾部元素？我正在尝试使用优先级队列实现波束搜索,一旦优先级队列已满,我想删除最后一个元素(具有最低优先级的元素).

谢谢!

我目前正在编写一个Android应用程序(API级别2.3.3),其中涉及从通过相机意图拍摄的照片中获取300个最高灰度值.接下来,对结果值执行函数(主要是数学和一些基于日历/时钟).我正在使用Eclipse /模拟相机.

相机将启动和拍照之间没有问题,那就是当我试图保存照片(当像素排序和数学/日历功能将发生),应用程序崩溃.

我用相机意图和主变量(Y)的'虚拟'值测试了应用程序,这很好用.

出了什么问题？

以下是相关的代码部分:

int[] pixels;   


    Button button = (Button) findViewById(R.id.button);

    button.setOnClickListener(new View.OnClickListener() {

        @Override
        public void onClick(View v) {

            String _path = Environment.getExternalStorageDirectory() + File.separator + "sunpic.jpg";
            File file = new File(_path);
            Uri outputFileUri = Uri.fromFile(file);
            Intent intent = new Intent(
            android.provider.MediaStore.ACTION_IMAGE_CAPTURE);
            intent.putExtra(MediaStore.EXTRA_OUTPUT, outputFileUri);
            startActivityForResult(intent, 1);

            }

    });
}

@Override
protected void onActivityResult(int requestCode, int resultCode, Intent data) {
    super.onActivityResult(requestCode, resultCode, data);
        switch(requestCode) {
            case (1): {
                if (resultCode == RESULT_OK) {
                    Uri outputFileUri = data.getData();
                    try …

正如您从标题中所知,我正在尝试使用PriorityQueue进行多处理.更确切地说,我想制作共享的PriorityQueue,编写了一些代码并且它没有像我预期的那样运行.

看看代码:

import time
from multiprocessing import Process, Lock
from Queue import PriorityQueue


def worker(queue):
    lock = Lock()
    with lock:
        for i in range(100):
            queue.put(i)

    print "worker", queue.qsize()


pr_queue = PriorityQueue()
worker_process = Process(target = worker, args = (pr_queue,))
worker_process.start()

time.sleep(5)    # nope, race condition, you shall not pass (probably)
print "main", pr_queue.qsize()

得到以下输出:

worker 100
main 0

发生了什么以及如何以正确的方式做我想做的事情？谢谢.

我们有一个问题,讨论如何priority_queue在C++中使用比较器.他给出了重载operator class(或struct)作为第三个参数,它工作正常.但bool功能不起作用.为什么？但它工作在罚款sort的<algorithm>.当我查看文档(priority_queue && algo/sort)时,它们都将其class Compare作为可选的第三个参数.

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

bool cmp (const int &a,const int &b){ return a > b; }

struct cmp2
{
    bool operator() (const int &p1,const int &p2)
    {
        return p1 > p2;
    }
};

int main ()
{
//  freopen("test.txt","r",stdin);
    int a[10];
    vector<int> b(10);
    sort( a , a + …

在PriorityQueue的构造函数中，我们可以传入一个像List或Set这样的集合，在线性时间内构建PriorityQueue。但是，这也意味着 PriorityQueue 将使用默认的 Comparator。

我想使用自己的比较器，因此除了最小堆之外，我还可以拥有其他东西。我能想到的唯一方法是将集合包装在 SortedSet 中并在其中放置一个自定义比较器。

有没有其他好的方法来做到这一点？

我试图使用heap实现一个示例程序，并且我能够 Push往返Pop于堆。我能够实现 Push 和 Pop 方法并按如下方式使用它们：

import "container/heap"

type Meeting struct {
    start int
    end int
}

func NewMeeting(times []int) *Meeting {
    return &Meeting{start: times[0], end: times[1] }
}

type PQ []*Meeting

func (pq PQ) Len() int {
    return len(pq)
}

func (pq PQ) Less(i, j int) bool {
    return pq[i].end < pq[j].end
}

func (pq PQ) Swap(i, j int) {
    pq[i], pq[j]  = pq[j], pq[i]
}


func (pq *PQ) Push(x interface{}) {
    item := …