堆首先是一个完全二叉树，堆分为小根堆和大根堆。小根堆，所有结点的左右子节点都不小于根节点；大根堆，所有结点的左右子节点都不大于根节点。优先级队列（priorityQueue）底层就是一个小根堆。目录
一、堆的创建
1、向下调整（以小堆为例）
2、创建堆
3、创建堆的时间复杂度
二、堆的插入和删除
1、堆的插入
2、堆的删除
三、堆的应用
1、堆排序
2、top-k问题 【求最小的K个数】
四、常用接口的介绍
1、PriorityQueue的特性
2、优先级队列的构造
一、堆的创建 1、向下调整（以小堆为例）
- 让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)
- 如果parent的左孩子存在，即:child < size， 进行以下操作，直到parent的左孩子不存在：
parent小于较小的孩子child，调整结束否则：交换parent与较小的孩子child，交换完成之后，parent中大的元素向下移动，可能导致子树不满足堆的性质，因此需要继续向下调整，即parent = child；child = parent*2+1; 然后继续2。
- parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标记
- 将parent与较小的孩子child比较，如果：
public void shiftDown(int[] elem,int parent,int len){
int cur=parent*2+1;
while(cur2、创建堆
对于普通序列，我们需要从它的第一个有左节点的父节点开始调整，知道整棵树满足堆的性质。
文章图片
3、创建堆的时间复杂度
堆必须是完全二叉树，满二叉树也是完全二叉树。由下面的计算，创建堆的时间复杂度为O(n).
文章图片
二、堆的插入和删除 1、堆的插入
- 将要插入的元素放在堆的最后，如果放不了，进行扩容
- 将新插入的节点向上调整，直到满足堆的性质
文章图片
【向上调整】
public void shiftUp(int elem[],int child){
int parent=(child-1)/2;
while(parent>=0){
if(elem[child]>elem[parent]){
swap(child,parent);
child=parent;
parent=(child-1)/2;
}else{
break;
}
}
}2、堆的删除
根据堆的性质，对删除的一定是堆顶元素。步骤如下：
- 将堆顶元素和最后一个元素交换
- 堆的元素个数减一
- 对堆顶元素进行向下调整
文章图片
三、堆的应用 1、堆排序
升序：创建大根堆【数据结构|堆（优先级队列）】
降序：创建小根堆
交换堆顶元素和堆得最后一个元素，进行向下调整，直到堆有序。
文章图片
2、top-k问题 【求最小的K个数】
top-k问题：求数据集合中前k个大或者小的元素，一般数据量都比较大。
文章图片
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] array=new int[k];
if(arr==null||arr.length<=k||k==0){
return array;
}
PriorityQueue queue=new PriorityQueue<>((a,b)->b-a);
int i=0;
for(;
i
四、常用接口的介绍
1、PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列。PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。
【PriorityQueue】使用的注意事项：
- 必须导入PeioriryQueue的包；
- 放置的元素必须是能够比较大小的，否则会抛出ClassCastException异常；
- 不能放置null元素，否则会抛出NullPointerException；
- 可以插入任意多的元素，内部会自动扩容；
- 底层使用了堆数据结构，默认是小堆。如果要构建大堆，则需要提供比较器。
PriorityQueue的扩容方式：
- 如果容量小于64时，是按照oldCapacity的2倍方式扩容的
- 如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
- 如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
PriorityQueue采用了：Comparble和Comparator两种方式。
1. Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法
2. 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现Comparator接口并覆写compare方法
// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator{
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
PriorityQueue p = new PriorityQueue<>(new IntCmp());
2、优先级队列的构造
构造器
功能介绍
PriorityQueue()
创建一个空的优先级队列，默认容量是11
PriorityQueue(int
initialCapacity)
创建一个初始容量为initialCapacity的优先级队列，注意：
initialCapacity不能小于1，否则会抛IllegalArgumentException异
常
PriorityQueue(Collection extends E> c)
用一个集合来创建优先级队列
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 数据结构|二叉树（题集（二））
- 数据结构|二叉树（题集（一））
- 数据结构|链表（题集）
- Java高级|原子变量、无锁算法和非阻塞机制
- 数据结构|七大常用排序
- Java工程师高薪训练营爱分享
- 拉钩Java工程师就业急训营
- 疯了！Spring 再爆惊天大漏洞。。
- 初学者能学会的数据结构与算法|数算部分-----第一节----算法的时空复杂度