java中PriorityQueue队列的使用

最近做力扣767. 重构字符串时用到了PriorityQueue，平时工作很少用到这个优先级队列，在此做个学习笔记

java.util.PriorityQueue继承自java.util.AbstractQueue抽象类，java.util.AbstractQueue实现了java.util.Queue接口：

PriorityQueue的特点：它会根据放进队列的元素的自然排序或者自定义排序把最小值或者最大值放到队列的头部，每次poll()或者peek()拿到的都是队列的最小值或者最大值。注意一点：它只保证队列头部的值是最大值或者最小值，队列里面的所有元素并不是有序的，队列其它元素的顺序都是任意的。如果要有序的遍历一个PriorityQueue，可以调用出队方法poll()：

 使用示例：

import java.util.Comparator;
import java.util.PriorityQueue;
 
public class Solution {
	
	public static void main(String[] args){
		Solution s = new Solution();
		Child th = s.new Child();
		th.studyPriorityQueue();
	}
	
	class Child {
		
		/**
		 * 在力扣767. 重构字符串的基础上
         * 把字符串"vvvlllo"转换成相邻字符不同的字符串
		 */
		public void studyPriorityQueue() {
			String str = "vvvlllo";
			int[] counts = new int[26];
			for (int i=0; i
				counts[str.charAt(i) - 'a']++;
			}
			PriorityQueue queue = new PriorityQueue<>(new Comparator() {
				@Override
				public int compare(Character c1, Character c2) {
					/** 
					 * 因为评论区看有个童鞋提出疑问：
					 * 每次从队列中取出2个字符的话，题目中没有保证他们总是按照特定顺序取，比如给定的字符串是aaabbb的话？
					 * 所以这里参考他们的想法，当字母出现次数相同时自然顺序较小的字母优先级更高
					 */
					// 如果字母出现的次数一样，则按自然顺序较小字母的优先级更高
					// 如果字母出现的次数不一样，则出现次数更多字母优先级更高
					return counts[c1-'a'] == counts[c2-'a'] ? c1 - c2 : counts[c2-'a'] - counts[c1-'a'];
				}
			});
			// 把所有出现的字母放到队列
			for (char c='a'; c<='z'; c++) {
				if (counts[c-'a'] > 0) {
					queue.offer(c);
				}
			}
			StringBuffer sb = new StringBuffer();
			while (queue.size() > 1) {
				// 每次取队列头部的字母
				Character c1 = queue.poll();
				sb.append(c1);
				Character c2 = queue.poll();
				sb.append(c2);
				// 对应字母次数减1，如果减1后还大于0重新放回队列
				if (--counts[c1-'a'] > 0) {
					queue.offer(c1);
				}
				if (--counts[c2-'a'] > 0) {
					queue.offer(c2);
				}
			}
			// 如果队列非空，肯定是还剩一个字母，直接取出拼到结果里面
			if (!queue.isEmpty()) {
				sb.append(queue.poll());
			}
			
			System.out.println(sb);
		}
	}
}