A Guide to PriorityQueue

桃扇骨 2024-03-04 07:39 88阅读 0赞

**原文链接：[https://blog.csdn.net/ohwang/article/details/116934308][https_blog.csdn.net_ohwang_article_details_116934308]**

--------------------

**PriorityQueue 又叫 优先队列**

--------------------

**注意1：  
PriorityQueue是用数组实现，数组大小可以动态增加，容量无限。  
优先队列采用的是堆排序（默认为最小堆）。堆排序只能保证根是最大（最小），整个堆并不是有序的。**

**注意2：  
非线程安全。线程安全可以用`PriorityBlockingQueue`。**

**注意3：  
不允许使用 `null` 元素。**

**注意4：  
`offer()`、`poll()`、`remove()` 、`add()` 时间复杂度为`O(log(n))` 。  
`remove(Object)` 和 `contains(Object)` 时间复杂度为`O(n)`。  
`peek`、`element` 、`size` 时间复杂度为`O(常量)`。**

**注意5：  
方法`iterator()`中提供的迭代器并不保证以有序的方式遍历优先级队列中的元素。  
如果需要按顺序遍历，可用`Arrays.sort(pq.toArray())`。**

**注意6： 可以在构造函数中指定如何排序。**

# 默认的初始容量（11）
    PriorityQueue(int initialCapacity)
    # 使用指定的初始容量创建一个 PriorityQueue，并根据其自然顺序来排序其元素。
    
    PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
    # 使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器comparator来排序其元素。

**注意7： 此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。**

--------------------

# 默认升序
    PriorityQueue<Integer> queue2 = new PriorityQueue<>(10);
    queue2.offer(11);
    queue2.offer(9);
    int len = queue2.size();
    for (int i = 0; i < len; i++) {
        
        System.out.println(queue2.poll());
    }
    //输出 9 11
    
    # 自定义降序
    PriorityQueue<Integer> queue = new PriorityQueue<>(10, (a, b) -> b - a);
    queue.offer(13);
    queue.offer(9);
    int len1 = queue.size();
    for (int i = 0; i < len1; i++) {
        
        System.out.println(queue.poll());
    }
    //输出 13 9

# 模拟业务使用
    PriorityQueue<People> queue = new PriorityQueue<>(11, (p1, p2) -> p2.age - p1.age);
    for (int i = 1; i <= 10; i++) {
        
        queue.add(new People("张" + i, (new Random().nextInt(100))));
    }
    while (!queue.isEmpty()) {
        
        System.out.println(queue.poll().toString());
    }
    
    class People {
        
        String name;
        int age;
        public People(String name, int age) {
        
            this.name = name;
            this.age = age;
        }
        public String toString() {
        
            return "姓名：" + name + " 年龄：" + age;
        }
    }
    
    姓名：张9 年龄：67
    姓名：张1 年龄：66
    姓名：张8 年龄：65
    姓名：张7 年龄：54
    姓名：张4 年龄：48
    姓名：张2 年龄：41
    姓名：张5 年龄：39
    姓名：张3 年龄：26
    姓名：张6 年龄：11
    姓名：张10 年龄：0

[https_blog.csdn.net_ohwang_article_details_116934308]: https://blog.csdn.net/ohwang/article/details/116934308