Java优先队列的使用

1. 优先队列的定义

PriorityQueue继承了Queue接口，底层默认是一个小根堆。

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

2. 常用方法

方法	描述
boolean offer(E e)	入队列
E poll()	出队列
E peek()	得到队首元素
int size()	返回集合中的元素个数

3. 自定义优先队列比较

PriorityQueue插入的元素不能是null 并且元素之间必须能够进行比较。

3.1 自定义比较器

// 定义的某个要比较类型的比较器
class IntegerComparator implements Comparator<Integer>{@Overridepublic int compare(Integer o1,Integer o2){// 如果第二个元素-第一个元素就是大根堆的实现方式，反之则为小根堆的创建方式，可以从源码去了解return o2-o1;}
}
public class TestDemo{public static void main(String[] args){PriorityQueue<Integer> maxHeap=new PriorityQueue<>(IntegerComparator);}
}

3.2 使用匿名内部类

// 定义的某个要比较类型的比较器
class IntegerComparator implements Comparator<Integer>{@Overridepublic int compare(Integer o1,Integer o2){// 如果第二个元素-第一个元素就是大根堆的实现方式，反之则为小根堆的创建方式，可以从源码去了解return o2-o1;}
}
public class TestDemo{public static void main(String[] args){PriorityQueue<Integer> maxHeap=new PriorityQueue<>(IntegerComparator);}
}

3.3 使用Lamda表达式

PriorityQueue<Integer> pq=new PriorityQueue<>((o1,o2)-> Integer.compare(o2,o1));

4. 补充堆排序的实现

class Solution {public int findKthLargest(int[] nums, int k) {int heapSize = nums.length;buildMaxHeap(nums, heapSize);for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {swap(nums, 0, i);--heapSize;maxHeapify(nums, 0, heapSize);}return nums[0];}public void buildMaxHeap(int[] a, int heapSize) {for (int i = heapSize / 2; i >= 0; --i) {maxHeapify(a, i, heapSize);} }public void maxHeapify(int[] a, int i, int heapSize) {int l = i * 2 + 1, r = i * 2 + 2, largest = i;if (l < heapSize && a[l] > a[largest]) {largest = l;} if (r < heapSize && a[r] > a[largest]) {largest = r;}if (largest != i) {swap(a, i, largest);maxHeapify(a, largest, heapSize);}}public void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}
}