Java 集合框架中提供了 PriorityQueue 和 PriorityBlockingQueue 两种类型的优先级队列，PriorityQueue 是线程不安全的，PriorityBlockingQueue 是线程安全的，下面主要介绍 PriorityQueue。
使用注意事项：
-
使用时必须导入包：
import java.util.PriorityQueue; -
PriorityQueue中放置的元素必须要能够比较大小 ，不能插入无法比较大小的对象，否则会抛出ClassCastException异常。 -
不能插入
null对象 ，否则会抛出NullPointerException。 -
PriorityQueue默认情况下是小堆 。 -
创建自定义大小堆的比较器写法如下所示：（以
Integer为例）
// 推荐使用 Comparator 而不是 Comparable，因为前者比较灵活、侵入性小
// 创建小堆
class lesscmp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
}
// 创建大堆
class greatercmp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
}
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 默认为小堆
pq.add(10);
pq.add(20);
pq.add(15);
while(!pq.isEmpty()) {
System.*out*.println(pq.poll());
};
PriorityQueue<Integer> pq1 = new PriorityQueue<>(new greatercmp());
pq1.add(10);
pq1.add(20);
pq1.add(15);
while(!pq1.isEmpty()) {
System.*out*.println(pq1.poll());
}
** // 使用lambda表达式创建大堆**
PriorityQueue<Integer> pq2 = new PriorityQueue<>((o1, o2) -> {return o1.compareTo(o2)});
pq2.add(10);
pq2.add(20);
pq2.add(15);
while(!pq2.isEmpty()) {
System.*out*.println(pq2.poll());
}
}
// 运行结果
10
15
20
20
15
10
20
15
10堆排序
-
升序 ：建大堆
-
降序 ：建小堆
-
时间复杂度：O(nlogn)
