快捷導(dǎo)航

Java中關(guān)于優(yōu)先隊(duì)列PriorityQueue的使用及相關(guān)方法

更新時(shí)間：2023年08月10日 10:23:11 作者：你的代碼沒bug

這篇文章主要介紹了Java中關(guān)于優(yōu)先隊(duì)列PriorityQueue的使用及相關(guān)方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教

Java中優(yōu)先隊(duì)列PriorityQueue的使用

簡(jiǎn)單使用

PriorityQueue<Integer> p = new PriorityQueue<>();

優(yōu)先級(jí)隊(duì)列從隊(duì)頭取元素，從隊(duì)尾添加元素。

默認(rèn)情況下，隊(duì)列中的數(shù)據(jù)是升序排序。

PriorityQueue<Integer> p = new PriorityQueue<>();
p.offer(5);
p.offer(1);
p.offer(3);
p.offer(6);
p.offer(8);
while(!p.isEmpty()) {
	System.out.println(p.poll());
}

運(yùn)行結(jié)果：

1
3
5
6
8

方法

和隊(duì)列的方法基本一樣

自定義排序規(guī)則

以下代碼改變排序規(guī)則，從大到小：

PriorityQueue<Integer> queue=new PriorityQueue<>((o1,o2)->o2-o1);
PriorityQueue<Integer> queue= new PriorityQueue<>(Comparator.reverseOrder());

根據(jù)HashMap的value值對(duì)HashMap的鍵值對(duì)排序

public static void main(String[] args) {
	HashMap<Integer, Integer> map = new HashMap<>();
	map.put(1, 2);
	map.put(3, 4);
	map.put(5, 6);
	Set<Map.Entry<Integer, Integer>> entries = map.entrySet();//獲取鍵值對(duì)
	//自定義優(yōu)先隊(duì)列的排序規(guī)則，隊(duì)列內(nèi)存放的數(shù)據(jù)類型是鍵值對(duì)
	//o1，o2都是鍵值對(duì)這樣的對(duì)象
	PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> {
		return o1.getValue() - o2.getValue();//根據(jù)值升序排序
	});
	for (Map.Entry<Integer, Integer> entry : entries) {
		queue.offer(entry);//將鍵值對(duì)放到優(yōu)先隊(duì)列中
    }
	while(!queue.isEmpty()) {
		System.out.println(queue.poll().getValue());
	}
}

運(yùn)行結(jié)果：

2
4
6

優(yōu)先隊(duì)列PriorityQueue (大根堆/小根堆/TopK問題)

PriorityQueue是從JDK1.5開始提供的新的數(shù)據(jù)結(jié)構(gòu)接口，它是一種基于優(yōu)先級(jí)堆的極大優(yōu)先級(jí)隊(duì)列。優(yōu)先級(jí)隊(duì)列是不同于先進(jìn)先出隊(duì)列的另一種隊(duì)列。每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素。

默認(rèn)情況下，PriorityQueue是小頂堆，如代碼所示

public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        queue.offer(6);
        while (!queue.isEmpty()){
            System.out.print(queue.poll() + " ");
        }
    }

輸出結(jié)果：

我們也可以通過以下方式來構(gòu)造大頂堆：

public static void main(String[] args) {
  PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 - o1);//降序
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        queue.offer(6);
        while (!queue.isEmpty()){
            System.out.print(queue.poll() + " ");
        }
    }

輸出結(jié)果：

Top K問題，力扣347和力扣692：

力扣347：給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k ，請(qǐng)你返回其中出現(xiàn)頻率前 k 高的元素。你可以按 任意順序 返回答案。

示例：

輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]

代碼如下：注意構(gòu)造小頂堆的時(shí)候(o1,o2)-> o1.getValue() - o2.getValue() 不能省略。

public int[] topKFrequent(int[] nums, int k) {
        //key為元素值，value為出現(xiàn)頻率
        HashMap<Integer,Integer> map = new HashMap<>();
        PriorityQueue<Map.Entry<Integer, Integer>> queue 
        = new PriorityQueue<>((o1,o2)-> o1.getValue() - o2.getValue());
        int[] res = new int[k];
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer, Integer> entry : entries) {
            queue.offer(entry);
            if(queue.size() > k){
                queue.poll();
            }
        }
        //留下的都是出現(xiàn)頻率最高的
        for(int i = 0; i < k; i++){
            Map.Entry<Integer, Integer> poll = queue.poll();
            res[i] = poll.getKey();
        }
        return res;

力扣692：給定一個(gè)單詞列表 words 和一個(gè)整數(shù) k ，返回前 k 個(gè)出現(xiàn)次數(shù)最多的單詞。返回的答案應(yīng)該按單詞出現(xiàn)頻率由高到低排序。如果不同的單詞有相同出現(xiàn)頻率， 按字典順序排序。

示例：

輸入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
輸出: ["i", "love"]
解析: "i" 和 "love" 為出現(xiàn)次數(shù)最多的兩個(gè)單詞，均為2次。注意，按字母順序 "i" 在 "love" 之前。

這題比上題難一點(diǎn)，因?yàn)楫?dāng)兩個(gè)單詞出現(xiàn)次數(shù)一致時(shí)還要考慮按字典序排序，其次是答案需要從高到底排序，這里主要體現(xiàn)在優(yōu)先隊(duì)列PriorityQueue的構(gòu)造上。

代碼如下：

public List<String> topKFrequent(String[] words, int k) {
        List<String> res = new ArrayList<>();
        //key為元素，value為出現(xiàn)頻率
        HashMap<String,Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word,map.getOrDefault(word,0) + 1);
        }
        PriorityQueue<Map.Entry<String,Integer>> queue = new PriorityQueue<>(
                ((o1, o2) -> {
                    if(o1.getValue() == o2.getValue()){
                        return o2.getKey().compareTo(o1.getKey());
                    }
                    return o1.getValue() - o2.getValue();
                })
        );
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
            queue.offer(entry);
            if(queue.size() > k){
                queue.poll();
            }
        }
        for(int i = 0; i < k; i++){
            res.add(queue.poll().getKey());
        }
        Collections.reverse(res);
        return res;
    }

注意o2.getKey().compareTo(o1.getKey())是按字典倒序，為什么要這么做呢，是因?yàn)槲覀冞@里用到小頂堆，所以每次poll出來的都是最小頻率元素，最后需要reverse一下，為了配合這個(gè)，所以我們構(gòu)造優(yōu)先隊(duì)列的時(shí)候采用字典倒序。