标签: priority-queue

我想在clojure中包装java的PriorityQueue类,以便在我的程序的另一部分中使用.我想弄清楚的是,是否有任何方法以lispy方式执行此操作并使优先级队列不可变.有没有什么好方法可以做到这一点,或者我是否会更好地使用PriorityQueue作为可变数据结构？

我在掌握并发队列的想法时遇到了一些麻烦.我理解一个队列是FIFO,或先到先服务,数据结构.

现在,当我们添加并发部分时,我将其解释为线程安全(请告诉我,如果这是不正确的),事情会变得有点模糊.并发性是指各种线程可以添加到队列中,还是从队列中删除(服务项目)的方式？并发是否为这种操作提供了一种排序感？

我非常感谢并发队列功能的一般描述.这里的类似帖子并不像我希望的那样普遍.

还有并发优先级队列这样的东西吗？它的用途是什么？

非常感谢,对此主题的任何简短解释或有用的链接.

我有一个java程序,就像这样

公共类PriorityQueueExample {

public static void main(String[] args) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(10);
    pq.add(1);
    pq.add(9);
    pq.add(2);
    pq.add(8);
    pq.add(3);
    pq.add(7);
    pq.add(4);
    pq.add(6);
    pq.add(5);
System.out.println(pq);

}

}

我的问题是为什么优先级队列不对它们进行排序.根据java规范,它实现了可比较并维护排序顺序(自然排序)

我的节目输出如下:[1,2,3,4,5,9,7,10,6,8]

我有以下问题:

如果被问到是否使用移位与乘法或除法(例如答案),请让JVM进行优化.

这里的示例:is-shifting-bits-faster-than-multiplying

现在我正在查看jdk源代码,例如Priority Queue,代码仅使用乘法和除法(有符号和无符号)进行移位.

理所当然地认为SO中的帖子是有效的答案我想知道为什么在jdk他们更愿意通过转移来做到这一点？

它是一些与性能无关的微妙细节吗？我怀疑它必须与上/下溢乘法和除法有关但我不确定.

有人有想法吗？使用移位是否能更好地处理溢出问题？或者只是味道问题？

我有一个priority_queue,我想修改它的一些内容(优先级值),那么队列会被使用吗？

这取决于它是否按下推/弹(更可能,因为你只需要"插入",而不是整体),或访问顶部或弹出时.

我真的想改变队列中的一些元素.像这样的东西:

priority_queue<int> q;

int a=2,b=3,c=5;
int *ca=&a, *cb=&b, cc=&c;

q.push(a);
q.push(b);
q.push(c); //q is now {2,3,5}

*ca=4;

//what happens to q?
// 1) {3,4,5}
// 2) {4,2,5}
// 3) crash

PriorityQueue的addAll方法的复杂性是什么.它是一次添加一个元素导致O(n log n)还是使用构建堆进程在O(n)时间内从无序元素创建堆？

我目前正在编写一个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 …

我刚刚学习了优先级队列,并且认为我会尝试使用类似的界面来表现它.

代码片段:

import java.util.PriorityQueue;

class kinga implements Comparable<Double> {
    double time=909.909;
    double d;

    public kinga(double a) {  
        this.d=a;
    }

    public int compareTo(Double d) {
        return Double.compare(d, time);
    }

    public static void main(String arg[]) {
        PriorityQueue<kinga> r=new PriorityQueue<kinga>();

        r.add( new kinga(4545.45));
        r.add( new kinga(45.4));
        r.add( new kinga(1235.45));

        System.out.println(r.poll()+" "+r.poll()+" "+r.poll());
    }
}

它编译但在线程"main"中 给出了Exception java.lang.ClassCastException: kinga cannot be cast to java.lang.Double.

这里有什么问题.有人能告诉我可比性和优先级队列的工作原理吗？

我试图接受一个字符串列表,并将它们添加到具有键和值的优先级队列中.Key是单词,值是单词的字符串值.然后我需要先用最高的字符串值对队列进行排序.优先级队列不允许我添加2个值.

public static List<String> pQSortStrings(List<String> strings) {
    PriorityQueue<String, Integer> q = new PriorityQueue<>();

    for (int x = 0; x < strings.size(); x++) {
        q.add(strings.get(x),calculateStringValue(strings.get(x)));
    }
    return strings;
}

tl; dr:我正在寻找Python的C++替代品heapq.heapreplace.

我必须以这样的方式处理最大堆(用作优先级队列),我弹出顶部元素,减去未指定的数字,然后再次推送该修改后的元素.我可以使用just来做这个pop_heap,push_heap但是这会做不必要的工作,因为它必须修改堆两次,每次重新建立堆不变量:

std::vector<unsigned> heap;
// ...
std::pop_heap(heap.begin(), heap.end()); // Re-establishes heap invariant.
decrease(heap.back());
std::push_heap(heap.begin(), heap.end()); // Re-establishes heap invariant again.

一个有效的界面可能看起来像这样:

decrease(heap.front()); // Modify in-place.
replace_heap(heap.begin(), heap.end());

是否有一些技巧让我让STL做我想做的事情或者我必须自己写作replace_heap？