目录
1. 优先级队列概念
队列是一种先进先出（FIFO）的数据结构，有些情况下，操作的数据可能带有优先级，出队列时需要优先级高的元素先出队列，这种情况下，数据结构应提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象，这种数据结构就是优先级队列（Priority Queue）。
2. 优先级队列的模拟实现
JDK1.8的PriorityQueue底层使用了堆这种数据结构，堆实际上就是在完全二叉树的基础上进行了调整。
2.1 堆的概念
堆就是以二叉树的顺序存储方式来存储元素，同时又要满足父亲结点存储数据都要大于儿子结点存储数据（也可以是父亲结点数据都要小于儿子结点数据）的一种数据结构。堆只有两种，即大堆和小堆，大堆就是父亲结点数据大于儿子结点数据，小堆则反之。
2.2 堆的存储方式
堆是一棵完全二叉树，可以用层序规则采用顺序存储方式，对于非完全二叉树，不适合使用顺序存储方式，因为为了还原二叉树，空间中必须要存储空节点，导致空间利用率比较低。
2.3 堆的创建
2.3.1 向下调整的时间复杂度
public class TestHeap {
private int usedSize;
int[] elem;
public void createHeap() {
for (int parent = (this.usedSize - 1 - 1) / 2; parent >= 0; parent--) {
siftDown(parent, this.usedSize);
}
}
private void siftDown(int parent, int usedSize) {
int child = 2 * parent + 1;
while (child < usedSize) {
if (child + 1 < usedSize && elem[child] < elem[child + 1]) {
child++;
}
if (elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
}
向下调整的时间复杂度为O(logN)
2.3.2 建堆时间复杂度
建堆的时间复杂度为O(N)
因为堆是完全二叉树，满二叉树也是完全二叉树，此处为了简化计算使用满二叉树来证明：
假设树高为h，第一层，2^0个节点，需要向下移动h-1层；第二层，2^1个节点，需要向下移动h-2层；第三层，2^2个节点，需要向下移动h-3层；... 第h-1层，2^(h-2)个节点，需要向下移动1层；
需要移动节点总的步数为：
T(N)=2^0*(h-1)+2^1*(h-2)+2^2*(h-3)+......+2^(h-2)*1
2*T(N)= 2^1*(h-1)+2^2*(h-2)+2^3*(h-3)+......+2^(h-1)*1
错位相减，得到：T(N)=2^h-1-h
由于N=2^h-1，则h=log2(N+1)
则，T(N)=N-log2(N+1)≈N
2.3.3 向上调整的时间复杂度
private void siftUp(int child){
int parent=(child-1)/2;
while(parent>=0){
if(elem[child]>elem[parent]){
swap(elem,child,parent);
child=parent;
parent=(child-1)/2;
}else{
break;
}
}
}向上调整的时间复杂度为O(N*logN)
2.4 堆的插入与删除
堆的插入需要两个步骤：
- 将元素放入到底层空间（空间不够时需扩容）
- 将最后新插入的节点向上调整，直到满足堆的性质
public void insert(int child) {
int parent = (child - 1) / 2;
while (child > 0) {
if (elem[parent] > elem[child]) break;
else {
swap(elem, child, parent);
child = parent;
parent = (child - 1) / 2;
}
}
}堆删除的一定是堆顶元素：
- 将堆顶元素与堆中最后一个元素交换
- 将堆中有效数据个数-1
- 对堆顶元素进行向下调整
已知小根堆为8,15,10,21,34,16,12,删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是(C)
A:1 B:2 C:3 D:4
3. 堆的应用
用堆作为底层结构封装优先级队列
堆排序利用堆的思想进行排序，分为两个步骤：
- 建堆（升序：建大堆；降序：建小堆）
- 利用堆删除思想进行排序
建堆和堆删除都用到了向下调整
4. 常用接口介绍
4.1 PriorityQueue的特性
- 使用时必须导入PriorityQueue所在的包
- PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则抛出异常
- 不能插入null对象，否则抛出异常
- 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
- 插入和删除元素的时间复杂度为O(logN)
- PriorityQueue底层使用了堆数据结构
- PriorityQueue默认情况下是小堆，即每次获取到的是最小元素
4.2 PriorityQueue常用接口介绍
PriorityQueue()：创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)：创建一个初始容量为initialCapacity的优先级队列，注意：initialCapacity不能小于1，否则抛异常
4.3 topK问题
面试题 17.14. 最小K个数 - 力扣（LeetCode）
topK问题：有N个元素，找出前K个最小的元素
第一种做法：整体排序
第二种做法：整体建立一个大小为N的小根堆
class Solution {
public int[] smallestK(int[] arr, int k) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
int[] ret = new int[k];
for (int x : arr) {
priorityQueue.offer(x);
}
for (int i = 0; i < k; i++) {
ret[i] = priorityQueue.poll();
}
return ret;
}
}第三种做法：把前K个元素创建为大根堆，遍历剩下的N-K个元素，和堆顶元素比较，如果比堆顶元素小，则堆顶元素删除，当前元素入堆
class Intcmp implements Comparator<Integer> {
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
}
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] ret = new int[k];
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Intcmp());
if (arr.length == 0 || k == 0)
return ret;
for (int i = 0; i < k; i++) {
priorityQueue.offer(arr[i]);
}
for (int i = k; i < arr.length; i++) {
int val = priorityQueue.peek();
if (arr[i] < val) {
priorityQueue.poll();
priorityQueue.offer(arr[i]);
}
}
for (int i = 0; i < k; i++) {
ret[i] = priorityQueue.poll();
}
return ret;
}
}