前言：队列是一种先进先出的数据结构，但是某时候有一些数据有优先级，比如打游戏时候突然来个电话。在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

1：堆概念

官方：如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
我自己简单认为就是把二叉树修改了一些，修改了存储方式，二叉树是一种链式存储，而堆是一种顺序存储是数组，分为了大根堆和小根堆

堆的一些特征：
1:堆是一颗完全二叉树
2:堆采用的是层序规则顺序存储结构，因为堆是一颗完全二叉树，非完全二叉树不适合顺序存储，会造成空间的浪费
2：堆的子节点的值不大于或者不小于其父亲结点的值
以小根堆为例：

一些重要的二叉树性质：

2：堆的创建(以小根堆为例)

问题：对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆呢？
我自己理解画的图的和写的代码：

public class TestHeap {public int usedSize;public int []elem;public TestHeap() {this.elem = new int[10];}public void initElem(int[] array) {for (int i = 0; i < array.length; i++) {this.elem[i] = array[i];usedSize++;}}// 时间复杂度：O(N)public void  createHeap() {//每个父亲节点for (int parent=(usedSize-1-1)/2;parent>=0;parent--) {sitfDown(parent,usedSize-1);//调整}}时间复杂度：O(log（n）)private void sitfDown(int parent, int i) {int child=2*parent+1;//先求出左孩子结点while(child<=i) { //结束条件child<useSize这里传过来的是usedSize-1if ((child+1<=i)&&elem[child]>elem[child+1]) {child++;//判断左右孩子的大小，如果左边大，就调整为右孩子结点}//判断父结点和子结点大小if(elem[parent]>elem[child]) {swap(elem,parent,child);//如果父节点大于就交换//继续往下调整parent=child;child=2*parent+1;}else  {//如果父子节点小于子结点之间结束循环，因为是从最后一颗树调整，所有下面的树就是小根堆。break;}}}private void swap(int array[],int parent, int child) {int temp=array[parent];array[parent]=array[child];array[child]=temp;}
}

注意事项：
子结点必须已经是小根堆
在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
这里主要注意一下结束条件，还要就是如果父亲结点比子结点小，直接跳出循环的理解，因为当父亲结点小于子节点时候，子节点本来已经就是小根堆了，父亲结点的值就不可能比子节点的值再小了。

建堆的时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

向上建堆的时间复杂度

3：堆的插入与删除

3.1 堆的插入

 public void offer(int val) {if(isFull()==true) {elem= Arrays.copyOf(elem,2*elem.length);}elem[usedSize]=val;upDown(usedSize,elem);usedSize++;}private void upDown(int usedSize, int[] elem) {int parent=(usedSize-1)/2;int child=usedSize;while(parent>=0) {if(elem[child]<elem[parent]) {swap(elem,parent,child);child=parent;parent=(child-1)/2;} else {break;}}}private boolean isFull() {return elem.length==usedSize;}
}

堆的插入总共需要两个步骤：

1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)
2. 将最后新插入的节点向上调整，直到满足堆的性质
3. 

3.2堆的删除

 public void  poll() {if (isEmpty()) {return;}swap(elem,0,usedSize-1);usedSize--;siftDown(0,usedSize-1);//调整}private boolean isEmpty() {return usedSize==0;}
}

注意：堆的删除一定删除的是堆顶元素。具体如下：

1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整
   

4：oj练习

top-k问题：最大或者最小的前k个数据。比如：世界前500强公司
top-k问题：最小的K个数

优化：
topk方法解决。

 public static int [] findmax(int []array,int k) {PriorityQueue<Integer> priorityQueue =new PriorityQueue<>();//k*log(K)for (int i = 0; i <k ; i++) {priorityQueue.offer(array[i]);}//(n-k)*log(k)for (int i = k; i <array.length ; i++) {int peek=priorityQueue.peek();if(peek<array[i]) {priorityQueue.poll();priorityQueue.offer(array[i]);}}int []elem=new int[k];for (int i = 0; i <k ; i++) {elem[i]=priorityQueue.poll();}return elem;}

5：堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆
   升序：建大堆
   降序：建小堆
2. 利用堆删除思想来进行排序
   建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
   

6接口介绍（底层代码的查看）

PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的

关于PriorityQueue的使用要注意：

1. 使用时必须导入PriorityQueue所在的包，即：
   import java.util.PriorityQueue;
2. 2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出
      ClassCastException异常
3. 不能插入null对象，否则会抛出NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容（自动扩容）
5. 插入和删除元素的时间复杂度为O（log（n）)；
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素

6.1常用三种构造方法

jdk17

在堆里面默认的是小堆，如果我们要建大堆就要设置比较器，给堆传入比较器。

// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
}
public class TestPriorityQueue {public static void main(String[] args) {PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());p.offer(4);p.offer(3);p.offer(2);p.offer(1);p.offer(5);System.out.println(p.peek());}
}

我们再了解一下jdk8的扩容机制

   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {int oldCapacity = queue.length;
// Double size if small; else grow by 50%int newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity + 2) :(oldCapacity >> 1));
// overflow-conscious codeif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}