淘宝联盟交钱建设网站,酒店网站素材,企业网站建设免备案,惠城网站制作1. 优先队列的定义
PriorityQueue继承了Queue接口#xff0c;底层默认是一个小根堆。
PriorityQueueInteger queuenew PriorityQueue();
2. 常用方法
方法描述boolean offer(E e)入队列E poll()出队列E peek()得到队首元素 int size() 返回集合中的元素个…1. 优先队列的定义
PriorityQueue继承了Queue接口底层默认是一个小根堆。
PriorityQueueInteger queuenew PriorityQueue();
2. 常用方法
方法描述boolean offer(E e)入队列E poll()出队列E peek()得到队首元素 int size() 返回集合中的元素个数
3. 自定义优先队列比较
PriorityQueue插入的元素不能是null 并且元素之间必须能够进行比较。
3.1 自定义比较器
// 定义的某个要比较类型的比较器
class IntegerComparator implements ComparatorInteger{Overridepublic int compare(Integer o1,Integer o2){// 如果第二个元素-第一个元素就是大根堆的实现方式反之则为小根堆的创建方式可以从源码去了解return o2-o1;}
}
public class TestDemo{public static void main(String[] args){PriorityQueueInteger maxHeapnew PriorityQueue(IntegerComparator);}
}3.2 使用匿名内部类
// 定义的某个要比较类型的比较器
class IntegerComparator implements ComparatorInteger{Overridepublic int compare(Integer o1,Integer o2){// 如果第二个元素-第一个元素就是大根堆的实现方式反之则为小根堆的创建方式可以从源码去了解return o2-o1;}
}
public class TestDemo{public static void main(String[] args){PriorityQueueInteger maxHeapnew PriorityQueue(IntegerComparator);}
}3.3 使用Lamda表达式
PriorityQueueInteger pqnew 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;}
}
