快捷導(dǎo)航

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

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

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

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

簡單使用

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

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

默認(rèn)情況下，隊列中的數(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());
}

運行結(jié)果：

1
3
5
6
8

方法

和隊列的方法基本一樣

自定義排序規(guī)則

以下代碼改變排序規(guī)則，從大到?。?/p>

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

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

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();//獲取鍵值對
	//自定義優(yōu)先隊列的排序規(guī)則，隊列內(nèi)存放的數(shù)據(jù)類型是鍵值對
	//o1，o2都是鍵值對這樣的對象
	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);//將鍵值對放到優(yōu)先隊列中
    }
	while(!queue.isEmpty()) {
		System.out.println(queue.poll().getValue());
	}
}

運行結(jié)果：

2
4
6

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

PriorityQueue是從JDK1.5開始提供的新的數(shù)據(jù)結(jié)構(gòu)接口，它是一種基于優(yōu)先級堆的極大優(yōu)先級隊列。優(yōu)先級隊列是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優(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：給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k ，請你返回其中出現(xiàn)頻率前 k 高的元素。你可以按 任意順序 返回答案。

示例：

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

代碼如下：注意構(gòu)造小頂堆的時候(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：給定一個單詞列表 words 和一個整數(shù) k ，返回前 k 個出現(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ù)最多的兩個單詞，均為2次。注意，按字母順序 "i" 在 "love" 之前。

這題比上題難一點，因為當(dāng)兩個單詞出現(xiàn)次數(shù)一致時還要考慮按字典序排序，其次是答案需要從高到底排序，這里主要體現(xiàn)在優(yōu)先隊列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())是按字典倒序，為什么要這么做呢，是因為我們這里用到小頂堆，所以每次poll出來的都是最小頻率元素，最后需要reverse一下，為了配合這個，所以我們構(gòu)造優(yōu)先隊列的時候采用字典倒序。