目錄

?前言：

1、PriorityQueue的特性

.2 PriorityQueue常用接口介紹

Ⅰ、PriorityQueue常見的構(gòu)造方法

?Ⅱ、常用的方法

Ⅲ、PriorityQueue的擴容方式：

?3、應用

?前言：

普通的隊列是一種 先進先出的數(shù)據(jù)結(jié)構(gòu)，元素在隊列尾追加，而從隊列頭刪除。在優(yōu)先隊列中，元素被賦予優(yōu)先級。當訪問元素時，具有最高優(yōu)先級的元素最先刪除。優(yōu)先隊列具有最高級先出 （first in, largest out）的行為特征。通常采用 堆數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。

在下面這篇文章中講解了堆。

八大排序之選擇排序_冷兮雪的博客-CSDN博客

Java 集合框架中提供了 PriorityQueue 和 PriorityBlockingQueue 兩種類型的優(yōu)先級隊列， PriorityQueue 是線 程不安全的， PriorityBlockingQueue 是線程安全的 ，本文主要介紹 PriorityQueue 。

?查看源碼發(fā)現(xiàn)：PriorityQueue繼承了AbstractQueue，并且初始容量為11，AbstractQueue又實現(xiàn)了Queue接口

?

關于PriorityQueue的使用要注意：

1. ?使用時必須導入PriorityQueue所在的包，即：?

   import java.util.PriorityQueue;

2. ?PriorityQueue中放置的元素必須要能夠比較大小，不能插入無法比較大小的對象，否則會拋出 ClassCastException異常
3. 不能插入null對象，否則會拋出NullPointerException
4. ?沒有容量限制，可以插入任意多個元素，其內(nèi)部可以自動擴容
5. 插入和刪除元素的時間復雜度為log?N
6. PriorityQueue底層使用了堆數(shù)據(jù)結(jié)構(gòu),
7. ?PriorityQueue默認情況下是小堆---即每次獲取到的元素都是最小的元素（如果要設置為大根堆的話需要重寫比較器來實現(xiàn)或者借助lambda表達式）

   package 選擇排序;
   
   import java.util.PriorityQueue;
   
   public class 優(yōu)先級隊列 {
       public static void main(String[] args) {
           PriorityQueue<Integer> queue=new PriorityQueue<>();
           queue.offer(4);
           queue.offer(2);
           queue.offer(3);
           queue.offer(7);
           queue.offer(9);
           System.out.println(queue.peek());//2
       }
   }
   

方法一：比較器

PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

方法二：lambda表達式

Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);

import java.util.Comparator;
import java.util.PriorityQueue;


public class 優(yōu)先級隊列 {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(4);
        queue.offer(2);
        queue.offer(3);
        queue.offer(7);
        queue.offer(9);
        System.out.println(queue.peek());//2
        PriorityQueue<Integer> queue1=new PriorityQueue<>((o1, o2) -> o2-o1);
        queue1.offer(4);
        queue1.offer(2);
        queue1.offer(3);
        queue1.offer(7);
        queue1.offer(9);
        System.out.println(queue1.peek());//9
    }
}

2 PriorityQueue常用接口介紹

Ⅰ、PriorityQueue常見的構(gòu)造方法

import java.util.PriorityQueue;

class Student implements Comparable<Student>{
    public int age;

    @Override
    public int compareTo(Student o) {//如果沒有比較器，則下面添加時則會報錯
        return this.age-o.age;
    }
}
public class 優(yōu)先級隊列 {

    public static void main(String[] args) {
        PriorityQueue<Student> queue=new PriorityQueue<>();
        queue.offer(new Student());
        queue.offer(new Student());
    }
}

?因為PriorityQueue不能插入無法比較大小的對象，需要實現(xiàn)比較器。

?Ⅱ、常用的方法

Ⅲ、PriorityQueue的擴容方式：

private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // overflow-conscious code
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

優(yōu)先級隊列的擴容說明：

• 如果容量小于64時，是按照oldCapacity的2倍方式擴容的
• 如果容量大于等于64，是按照oldCapacity的1.5倍方式擴容的
• 如果容量超過MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE來進行擴容

?3、應用

經(jīng)典優(yōu)先級隊列問題——TOP-K問題：最大或者最小的前k個數(shù)據(jù)

面試題 17.14. 最小K個數(shù) - 力扣（Leetcode）

class Solution {
    public int[] smallestK(int[] arr, int k) {
// 參數(shù)檢測
        if (null == arr || k <= 0)
            return new int[0];
        PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
// 將數(shù)組中的元素依次放到堆中
        for (int i = 0; i < arr.length; ++i) {
            q.offer(arr[i]);
        }
// 將優(yōu)先級隊列的前k個元素放到數(shù)組中
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = q.poll();
        }
        return ret;
    }
}

?692. 前K個高頻單詞 - 力扣（Leetcode）

?這題既可以使用HashMap也可以使用優(yōu)先級隊列。

優(yōu)先級隊列思想

我們可以創(chuàng)建一個小根優(yōu)先隊列（顧名思義，就是優(yōu)先隊列頂端元素是最小元素的優(yōu)先隊列）。我們將每一個字符串插入到優(yōu)先隊列中，如果優(yōu)先隊列的大小超過了 k，那么我們就將優(yōu)先隊列頂端元素彈出。這樣最終優(yōu)先隊列中剩下的 k個元素就是前 k?個出現(xiàn)次數(shù)最多的單詞。文章來源地址http://www.zghlxwxcb.cn/news/detail-434570.html

到了這里，關于優(yōu)先級隊列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！