目录
本篇主要内容总结
（1）优先级队列底层是堆来实现的
（2）堆的本质是完全二叉树 ，堆有大根堆和小根堆
（3）大根堆：根节点最大的堆； 小根堆：根节点最小的堆
（4）堆的创建实现：大根堆为例
大根堆创建：孩子结点和根节点比较交换，核心思想：向下调整 时间复杂度O(n)
堆的插入：插入到最后一个位置，和根结点交换，核心思想：向上调整
堆的删除：只能删除堆顶，然后重新向下调整组成新的大根堆
插入和删除时间复杂度O（log n）
（4）priorityQueue建堆是小根堆，如果要建立大根堆就要写比较器
（5）priorityQueue添加元素，要写明比较的类型才能添加
（6）top-K问题：前K个最大的元素建小根堆；前K个最小的元素建大根堆
第K个最大元素建小根堆 拿栈顶； 第K个最小元素建大根堆 拿栈顶
（7）堆排序：升序：大根堆 降序：小根堆
核心思想：堆元素的删除
在说堆的概念之前，先说一下堆的常用方法，从这个方向来写这篇文章
堆的常用方法有
（1）用来构建优先级队列
（2）支持堆排序（大堆或小堆）
（3）top-k问题
1. 优先级队列（Priority Queue）
优先级队列 ：是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。
优先级队列相对于普通队列应该提供两个最基本的操作，
（1）返回最高优先级对象（2）添加新的对象
在JDk1.8中的优先级队列底层使用了堆
2.堆的概念
简单的说 ，堆这种数据结构本质上就是一个完全二叉树
并且堆中某个结点的值总是不大于或不小于其父结点的值
小堆：根节点最小的堆，满足Ki <= K2i+1 且 Ki <= K2i+2
大堆：根节点最大的堆, 满足Ki >= K2i+1 且 Ki >= K2i+2
3.堆的存储方式
堆是一颗完全二叉树，所以按照层序来看，可以采用顺序数组的存储方式
但是非完全二叉树就不适用于顺序存储了，这是因为非完全二叉树如果有空结点，那顺序存储也要存储这个空节点，这就造成空间上的浪费
i表示孩子结点，父亲结点（i-1）/ 2
i表示根节点 ，左孩子 2 * i + 1 右孩子 2 * i + 2
4.堆的创建
5.用堆模拟实现优先级队列
按照大根堆来创建
先写一个数组，按顺序存储的方式
public int[] elem;
public int userSize;//当前堆中有效的元素数据个数
public MyHeap() {
this.elem = new int[10];
this.userSize = 0;
}
public void initArray(int[] array) {
elem = Arrays.copyOf(array,array.length);
userSize = elem.length;
}(1) 创建堆
先写一个向下调整的方法
/**
* @param parent: 每颗子树的根节点下标
* @param len:每颗子树的结束位置
* @description 向下调整
*/
private void shiftDown(int parent,int len) {
int child = 2*parent+1;//左孩子
//必须要有左孩子
while(child < len) {
//如果一定有右孩子。那就判断 左孩子和右孩子大小，谁大保存谁
if(child + 1 < userSize && elem[child] < elem[child+1]) {
child++;
}
//交换 比较孩子和根大小交换 然后根节点往下走继续必须
if (elem[child] > elem[parent]) {
swap(elem,child,parent);
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}再写一个交换根和孩子的方法
//交换 比较孩子和根大小交换
private void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}然后通过循环每个结点，向下调整，然后创建好这棵树
/**
*建堆：大根堆
*时间复杂度O(n)
*/
public void createHeap() {
for (int parent = (userSize-1-1)/2; parent >= 0 ; parent--) {
shiftDown(parent,userSize);
}
}分析一下建堆的时间复杂度O(n)
（2）堆的插入
先写一个方法来判断空间满不满
public boolean isFull() {
return userSize == elem.length;
}再写一个向上调整
//向上调整
private void shiftUp(int child) {
int parent = (child - 1) / 2;
while(child > 0) {
if(elem[child] > elem[parent]) {
swap(elem,child,parent);
child = parent;
parent = (child - 1) / 2;
}else {
break;
}
}
}最后再写堆的插入，如果空间满了就扩容，然后再向上调整，变成新的大根堆
//堆的插入
public void offer(int x) {
if (isFull()) {
elem = Arrays.copyOf(elem,2*elem.length);
}
this.elem[userSize] = x;
userSize++;
shiftUp(userSize-1);
}（3）堆的删除（优先级队列删除，只能删除堆顶的元素）
再删除前，先要看堆是不是空的
public boolean isEmpty() {
return userSize == 0;
}然后再删除堆顶元素
//堆的删除 只能删除堆顶元素
public int poll() {
if (isEmpty()) {
return -1;
}
int old = elem[0];
//1.交换
swap(elem,0,userSize-1);
//2.有效元素个数-1
userSize--;
//3.栈顶元素向下调整
shiftDown(0,userSize);
return old;
}看几个选择题把
1.已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是
(C)A: 1 B: 2 C: 3 D: 4
2.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是 ()
A: [3
，
2
，
5
，
7
，
4
，
6
，
8] B: [2
，
3
，
5
，
7
，
4
，
6
，
8]C: [2
，
3
，
4
，
5
，
7
，
8
，
6] D: [2
，
3
，
4
，
5
，
6
，
7
，
8]
6.PriorityQueue常用接口介绍
6.1 PriorityQueue的特点
（1）首先最重要的先明白priorityQueue建堆是小根堆
public static void main(String[] args) {
//默认是小根堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(45);
priorityQueue.offer(12);
priorityQueue.offer(55);
priorityQueue.offer(66);
System.out.println(priorityQueue.peek());
}
可以看到这里打印的是12所以是priorityQueue是小根堆
如果要建堆为大根堆，那就要写比较器Comparator了
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
}（2） 在priorityQueue使用offer添加元素时，一定要明确比较的规则，然后再添加
如果是直接这样比较的话，offer不知道以什么规则比较然后添加，就会报错。
public static void main(String[] args) {
PriorityQueue<Fruit> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(new Fruit() );
priorityQueue.offer(new Fruit() );
}所以这里必须告诉offer以什么方式比较添加，
比如说这里实现comparable接口
class Fruit implements Comparable<Fruit>{
public int age;
//必须告诉priorityQueue.offer 以什么方式比较添加元素
@Override
public int compareTo(Fruit o) {
return this.age - o.age;
}
}（3）不能插入null对象，否则会抛出NullPointerException异常
（4）可以插入任意多个元素，会自动扩容，没有容量限制
（5）插入和删除元素的时间复杂度为O(log n),建栈的时间复杂度O（n）
6.2 PriorityQueue几种常见的构造方式
（1）PriorityQueue() 初始默认容量为11
（2）PriorityQueue(int initialCapacity)
（3）PriorityQueue(Collection<? extends E> c)
（4）PriorityQueue(int initialCapacity, Collection<? super E> comparator
7.top-k问题
适用情况，在数据量比较大时，求数据集合中前K个最大的元素或者最小的元素
比如说求很多个元素的前k个最大的元素
思路1：
（1）将这些元素，全部放进大根堆中，堆顶的元素就是最大的值
（2）然后出k次，就能得到前k个最大的值，并且每出一次都会进行向下调整，变成新的大根堆
public static void topK1(int[] array, int k) {
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for (int i = 0; i < array.length; i++) {
maxPQ.offer(array[i]);
}
for (int i = 0; i < k; i++) {
int val = maxPQ.poll();
System.out.println(val);
}
System.out.println();
}
public static void main(String[] args) {
int[] array = {16,15,22,155,89,12,45};
topK1(array,3);
} 
缺点：数字有多少，这个堆就有多大，时间复杂度是O(n*log n)
思路2：
（1）求前K个最大的元素，建立大小为K的小根堆
（2）然后用剩下的集合里面的元素轮流和堆顶元素比较，如果剩下集合里面的元素比堆顶的元素大，那就替换掉堆顶的元素
（3）然后向下调整，变成新的小根堆，此时这个堆中的元素就是前K个最大元素
差不多和前面一样的方法，不同的是（1）求前K个最小的元素，要建立大根堆（2）比较的时候谁小，就把小的放在堆顶
力扣链接： 面试题 17.14. 最小K个数 – 力扣（LeetCode）
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] ret = new int[k];
if(k == 0) return ret;
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(k,new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for (int i = 0; i < arr.length; i++) {
if(maxPQ.size() < k) {
maxPQ.offer(arr[i]);
}else {
//获取到堆顶元素
int top = maxPQ.peek();
//找前k个最小的
if(arr[i] < top) {
maxPQ.poll();
maxPQ.offer(arr[i]);
}
}
}
for (int i = 0; i < k; i++) {
ret[i] = maxPQ.poll();
}
return ret;
}
}（1）前面求前K个最大的元素时，建立的小根堆，按照规则，到最后栈中全部都是前K个最大的元素，然后栈顶就是所要求得的第K大的元素
（2）前面求前K个最小的元素时，建立的大根堆，按照规则，到最后栈中全部都是前K个最小的元素，然后栈顶就是所要求得的第K小的元素
8.堆排序
如果是将堆排成一个升序的，那就建立大根堆，操作如下
public void heapSort() {
int end = userSize -1;
while(end > 0) {
swap(elem,0,end);
shiftDown(0,end);
end--;
}
}
如果是将堆排成一个降序的，那就建立小根堆，操作和上面类似
一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为 (C)A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5)D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/91247.html
