一、优先级概念
什么是优先级：比如女士优先，个子低的优先排到前面去，有一部分数据具备优先级，要以优先级的顺序将顺序存储起来。
前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列
priorityQueue是二叉树的完全二叉树，只不过是用数组来进行顺序存储
PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。
二、堆的概念
所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki 且 Ki= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
小根堆：根节点的大小小于孩子节点
大根堆：根节点的大小大于孩子节点
三、堆的存储方式
从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，
完全二叉树：数组的每一个位置被充分使用
一般二叉树：有的位置被浪费掉没有存储值
所以对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。
四、堆的创建与方法实现
import java.util.Arrays;
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap(){
this.elem = new int[10];
}
public void init(int[] array){
for(int i = 0;i<array.length;i++){
elem[i] = array[i];
usedSize++;
}
}
//把elem数组当中的数据 调整为大根堆
public void createHeap(){
int size = usedSize;
for(int parent = (size-1-1)/2;parent>=0;parent--){
siftDown(parent,size);
}
}
private void swap(int i,int j){
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}
//每棵子树向下调整 知父亲求孩子
public void siftDown(int parent,int end){
int child = 2*parent+1;
while(child<end){
if(child+1<end&&elem[child]<elem[child+1]){
//找到大的
child++;
}
//chile下标就是左右孩子最大值
if(elem[child]>elem[parent]){
swap(child,parent);
parent = child;
child = 2*parent+1;
}else{
break;
}
}
}
//调整为小根堆
public void siftDown2(int parent,int end){
int child = 2*parent+1;
while(child<end){
if(child+1<end&&elem[child]>elem[child+1]){
//找出最小
child++;
}
//chile下标就是左右孩子最大值
if(elem[child]<elem[parent]){
swap(child,parent);
parent = child;
child = 2*parent+1;
}else{
break;
}
}
}
//插入
public void offer(int val){
if(isFull()){
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize] = val;
usedSize++;
siftUp(usedSize-1);
}
//向上调整成大根堆,知孩子求父亲
public void siftUp(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;
}
}
}
//向上调整复杂度O(N*logN)
public boolean isFull(){
return usedSize==elem.length;
}
//删除第一个节点 将0下标与最后一个节点交换，再向下调整
public int poll(){
if(isEmpty()){
return -1;
}
int old = elem[0];
swap(0,usedSize-1);
usedSize--;
siftDown(0,usedSize);
return old;
}
public boolean isEmpty(){
return usedSize==0;
}
//数组排序，从小往大排，建立大根堆，从大往小排建立小根堆
public void heapSort(){
int endIndex = usedSize-1;
//O(N)
while(endIndex>0){
swap(0,endIndex);
siftDown(0,endIndex);//调整成大根堆O(logN)
endIndex--;
}
//O(N*logN)
}
}
对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆呢？
调整大根堆方法：从整棵树的最后一棵子树开始调整，每次让根节点与左右孩子比较，如果根节点比左右孩子的最大值都小，就交换根节点和孩子最大值。（小根堆同理）
上图就是大根堆
向下调整时间复杂度：约为N
Tn = 2^0*(h-1)+2^1*(h-2)+...+2^(h-2)*1+2^(h-1)*0
2Tn = 2^1*(h-1)+2^2*(h-2)+...+2^(h-1)*1
两式错位相减Tn = -2^0(h-1)+2^1+2^2+.....+2^(h-1)=-h-1+2^h
h = log以2为底(N+1)
Tn = -log(N+1)-1+N+1 = N-log(N+1)
n越来越大Tn约等于N
向上调整时间复杂度为N*logN
五、PriorityQueue常用接口介绍
1、优先级队列的构造（无构造器）
| 构造器 | 功能介绍 |
| PriorityQueue（） | 创建一个空的优先级队列，默认容量是11 |
| PriorityQueue（int initialCapacity） | 创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则会抛IllegalArgumentException异 常 |
| PriorityQueue（Collection<? extends E> c) | 用一个集合来创建优先级队列 |
public static void main(String[] args) {
//堆是队列实现的，叫优先级队列,数组实现
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(12);
priorityQueue.offer(5);
priorityQueue.offer(57);
System.out.println(priorityQueue.peek());//结果是5 所以默认是小根堆，也可以改为大根堆，以后讲
Queue<Integer> queue = new PriorityQueue<>();
//PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的
PriorityBlockingQueue<Integer> priorityBlockingQueue = new PriorityBlockingQueue<>();//多线程下推荐使用
}2、 功能
| 函数名 | 功能介绍 |
| boolean offer(E e) | 插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度，注意：空间不够时候会进行扩容 |
| E peek() | 获取优先级最高的元素，如果优先级队列为空，返回null |
| E poll() | 移除优先级最高的元素并返回，如果优先级队列为空，返回null |
| int size() | 获取有效元素的个数 |
| void clear() | 清空 |
| boolean isEmpty() | 检测优先级队列是否为空，空返回true |
offer功能
给比较器
未给比较器
将key强转为Comparable，所以需要实现Comparable接口，未实现就会出现类型转换异常
比如：如果创建student类的堆，如果未实现接口就会抛出异常
compareTo可以实现大堆小堆的转换
比较器
默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
| 提供比较器构造 | 功能介绍 |
public PriorityQueue(Comparator<? super E> comparator) | 可以改为大堆创建 |
PriorityQueue(int initialCapacity, Comparator<? super E> comparator) | 可以大堆创建初始容量为initialCapacity的优先级队列 |
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);//小根堆，如果o1和o2互换就是大根堆
}
}注意：
1、使用时必须导入PriorityQueue所在的包
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常
3. 不能插入null对象，否则会抛出NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5. 插入和删除元素的时间复杂度为
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素
top-k：最小的k个数
public static int[] smallestK(int[] arr,int k){
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
priorityQueue.offer(arr[i]);//时间复杂度NlogN
}
int[] tmp = new int[k];
for (int i = 0;i<k;i++){
int val = priorityQueue.poll();//时间复杂度k*logN
tmp[i] = val;
}
//整个时间复杂度是（N+k)logN，不是真的top-k的解法
return tmp;
}
最小的k个数->建立大小为k的大根堆
最大的k个数->建立大小为k的小根堆
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);//大根堆，如果o1和o2互换就是小根堆
}
}
public static int[] smallestK2(int[] arr,int k){
int[] tmp = new int[k];
if(k==0){
return tmp;
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new IntCmp());//大小为k的大根堆
for (int i = 0; i < k; i++) {
maxHeap.offer(arr[i]);//K*logK
}
//遍历剩下的元素
for (int i = k;i<arr.length;i++){
int val = maxHeap.peek();
if(val>arr[i]){
maxHeap.poll();
maxHeap.offer(arr[i]);
}
}//（N-K)*logK
tmp = new int[k];
for (int i = 0;i<k;i++){
tmp[i] = maxHeap.poll();//时间复杂度k*logN
}
return tmp;
//时间复杂度N*logK
}
