标签: priority-queue

来自维基百科：

排序列表实现：就像超市的收银台一样，但重要的人可以在不太重要的人面前“插队”。（O(n) 插入时间，O(1) 下次获取时间，O(n*log(n)) 构建时间）

我认为如果用二分查找算法来查找插入位置，插入时间复杂度应该是O(log(n))。这里我把作业的到达顺序作为优先级因素。

那么是我错了还是维基百科错了？

更新：根据 TAOCP 列表的严格定义：

线性列表是 n >=0 个节点 X 1 , X[2], ... , X[n] 的序列，其基本结构属性仅涉及项目之间出现在一行中时的相对位置。

我假设维基百科引用的列表不是链接列表，它可能是数组。

谢谢。

我有一个Java PriorityQueue用于从我称为Node的特定类中对对象进行排序.我希望它通过getData()方法对节点进行排序.我尝试了以下代码(使用比较器),但它没有用.当我调用优先级队列的"poll"方法时,它首先没有返回最低结果,而是以看似随机的顺序返回.我如何解决它？谢谢!

PriorityQueue<Node> pq = new PriorityQueue<Node>(hm.size(),
        new Comparator<Node>( ) {
            // override the compare method
            public int compare(Node i, Node j) {
                if (i.getData()<j.getData()){
                                        return i.getData(); //It should sort by the Node's getData method.
                                    }
                                    return j.getData();

我的问题可能看起来很幼稚，但我真的不明白这个问题，因为我只是数据结构课程的新手。我知道最大和最小堆是如何工作的，但我不确定堆是否是实现优先级队列的隐式数据结构。

我想建立节点的优先级队列,其中节点的优先级是它们的频率.但是输出不包含正确位置的第一个元素,其余都在正确的位置.

    import java.util.*;
class node implements Comparable<node>{
        char key;
        int freq;
        node(){}
        node(char k,int f){
                key=k;
                freq=f;
        }
    public int compareTo(node n){
            if(freq>n.freq)return 1;
            return 0;
        }
}

public class test{
    public static void main(String[] args){
        node x=new node('x',4);
        node a=new node('a',2);
        node b=new node('b',1);
        node c=new node('c',7);
        PriorityQueue<node> q = new PriorityQueue<node>();

        q.offer(a);
        q.offer(b);
        q.offer(c);
        q.offer(x);

        while(!q.isEmpty()){
            node d=q.poll();
            System.out.println(d.key+" "+d.freq);
        }
    }
}   

输出:

    a 2
    b 1
    x 4
    c 7

不应该订购b,a,x,c谢谢.

我想编写一个程序,可以按优先级队列对项目进行排序

但是下面的代码不起作用,我不知道问题

任何帮助？提前感谢您的关注

public class SortingASequenceByPriorityQueue {

public static void main(String[] args) {  
    PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>(1000, new Comparator<Integer>() {    

            public int compare(Integer w1, Integer w2) {                           
                if(w1.intValue()> w2.intValue())
                    return 1;
                else if( w1.intValue()< w2.intValue())
                    return -1;
                return 0;
            }        
        });    

         pQueue.add(12);    
         pQueue.add(1);     
         pQueue.add(5);    
         pQueue.add(22);    
         pQueue.add(3);    
         pQueue.add(2);    
         pQueue.add(124);    
         pQueue.add(14);    
         pQueue.add(111);    
         pQueue.add(9);    
         pQueue.add(30);    

        Object[] ar = pQueue.toArray();    
        for (int i = 0; i< ar.length; i++){    
            System.out.println(ar[i].toString());    
        }   
}  

}  

输出是这样的:

1 3 2 14 9 5 124 22 111 12 …

我对二进制搜索树和二进制堆上的find_min操作的运行时有些困惑.我知道在二进制堆中返回min是一个O(1)操作.我也理解为什么理论上,返回二进制搜索树中的最小元素是O(log(N))操作.令我惊讶的是,当我读到C++ STL中的数据结构时,文档声明将迭代器返回到映射中的第一个元素(与返回最小元素相同)是在恒定时间内发生的!难道这不能以对数时间返回吗？我需要有人帮助我理解C++正在做什么,以便在不变的时间内返回.因为那时,在C++中真正使用二进制堆是没有意义的,因此地图数据结构将支持在常量时间中检索min和max,在O(log(N))中删除和搜索并保持一切排序.这意味着数据结构具有BST和二进制堆的优点,所有这些都捆绑在一起!

我和一位采访者谈论过这个问题(不是真正的争论),但我试图向他解释,在C++中,C++(这是一种自平衡的二元搜索树)中的map中的min和max返回是在恒定的时间内发生的.他感到困惑,不停地说我错了,二进制堆是要走的路.澄清将非常感激

我需要将数字按升序存储在队列中。
我使用优先级队列，该优先级队列先存储较高的值，即以降序存储。

priority_queue<int>q;

可以命令它们增加吗？
我该怎么做才能使数据顺序增加？

我在将对象节点添加到 PriorityQueue 时遇到了麻烦，我不知道为什么。当我添加节点 a 时，它没有问题。

PriorityQueue<Node> q = new PriorityQueue<Node>();
Node a = new Node('a', 1);

q.add(a);

但是如果我添加第二个节点，它会抛出一个异常，说“java.lang.ClassCastException：节点不能被强制转换为 java.lang.Comparable”

PriorityQueue<Node> q = new PriorityQueue<Node>();
Node a = new Node('a', 1);
Node b = new Node('b', 2);

q.add(a);
q.add(b);

我的节点类如下：

public class Node {
    public int count;
    public char character;
    public Node left;
    public Node right;

    public Node(char character, int count) {
        this(character, count, null, null);
    }

    public Node(char character, int count, Node left, Node right) {
        this.count = count;
        this.character …

我有一个字符串数组列表，它们作为键放入映射中。该映射的值是字符串出现的频率。

我想读取 20 个最常见的字符串，因此我使用实现最大堆结构的 PriorityQueue。

尽管其元素的参数类型似乎是正确的，但我无法添加到优先级队列。

static Map<String, Integer> mapGuy = new HashMap<>();
private static PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>();

    public static List<String> head() {

        if (map.size() == 0){
            List<String> res = new ArrayList<>();
            return res;
        }

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            pq.offer(entry);
        }

        List<String> frequentGrams = new ArrayList<>();
        int counter = 0;
        /*
         * the counter this determines that you only add 20 items to frequentGrams
         * 
         * the while loop stops incrementing if there are …

我对 Java 中优先队列的初始容量的使用感到困惑。如官方文档所示，有一个以初始容量作为参数的构造函数。但是当我使用该构造函数指定初始容量并开始将整数放入其中时，优先级队列的大小变得大于初始容量。

例如，我将一个 PQ 的初始容量指定为 3，并将 10 个不同的数字放入其中，以便我可以得到第 3 个最小的数字，但结果是该队列中有 10 个数字。为了解决这个问题，我总是不得不手动删除一些数字，所以我想知道初始容量是如何工作的，或者在这种情况下我应该使用初始容量。

谢谢！