【Java数据结构】优先级队列（堆）
优先级队列
队列是一种先进先出的数据结构，但是有些情况下操作的数据可能带有优先级，一般出队时需要优先级高的先出队，所以就有了优先级队列的概念。优先级队列提供两个基本操作，一个是返回最高优先级对象，一个是添加新的对象。
堆
而且这个优先级队列的底层运用了堆的知识，优先级队列是顺序存储的二叉树，堆则是优先级队列调整为完全二叉树。堆的存储方式是在一个一维数组里，它又分大堆（堆中根结点的值总是大于左右结点）和小堆（堆中根结点的值总是小于左右结点）。堆是通过层序按顺序存储的（利用数组和完全二叉树可以充分利用数组内空间避免浪费）
例：假如现在有一个集合{27,15,19,18,28,34,65,49,25,37}的数据，怎么将它创建成堆？
首先我们先将其集合转成堆的结构（完全二叉树），将其转成后发现并不符合堆的性质，所以我们还需要进行调整，调整成大堆或小堆。不管是小堆还是大堆都要从根结点开始向下调整，所以这个方法就是向下调整，下面以大堆为例。
从最后一个结点开始，先找到最后一个结点的父结点，然后对比父结点的左右结点（如果没有右结点直接比较左结点），将孩子结点指向值大的那个，然后就对比父结点和孩子结点，如果父结点小将两个节点交换即可。这个父结点逐减减1直至结点不再存在（即小于0），但是要注意的就是并不是每个父结点都有孩子结点，所以找孩子结点时需要限制条件（孩子结点要小于最后一个结点）。
public class priorityQueue {
private int[] elem;
private int usedsize;
public priorityQueue(){
elem = new int[11];
}
public void init(int[] arr){
for (int i = 0; i < arr.length; i++){
this.elem[i] = arr[i];
usedsize++;
}
}
public void maxpriority(){
for (int p = (usedsize - 1)/2; p >= 0; p--){
shiftdown(p, usedsize);
}
}
//向下调整
private void shiftdown(int parent, int usedsize){
int child = (2*parent)+1;
while (child < usedsize){
if (child+1 < usedsize && elem[child] < elem[child+1]){
child++;//将孩子结点指向值大的那个结点
}
if (elem[parent] < elem[child]){
swap(parent, child);
parent = child;
child = parent*2+1;
}else{
break;
}
}
}
//交换父结点和孩子结点
private void swap(int i, int j){
int t = elem[i];
elem[i] = elem[j];
elem[j] = t;
}
}现在我们来计算一下它的复杂度，它的复杂度 = 该层结点数*该层调整高度的总和，再通过一系列操作就能知道向下调整的复杂度，所以采用向下调整建堆的时候复杂度为O(n)。
堆的插入和删除
插入：插入是从一个原先就是堆中插入，方法是先将要插入的结点放入二叉树中最末尾，然后再对整棵二叉树进行调整，这个过程称向上调整。
插入结点前也需要判断数组的容量是否可以添加一个元素（即判断数组是否满），然后将结点添加到最后再调整，调整从最后一个结点开始，向上调整直至整棵树符合堆的性质（大堆或小堆，全篇以大堆为头），需要从最后一个结点找到其父结点比较大小，插入的结点小的话直接终止比较即可，如果比父结点大则需要将两者交换，然后将孩子结点变成父结点，再找孩子结点的父结点，一直循环，直至孩子结点等于0就停止循环。
//交换两个结点
private void swap(int i, int j){
int t = elem[i];
elem[i] = elem[j];
elem[j] = t;
}
//向上调整
public void offer(int val){
if (isFull()){
this.elem = Arrays.copyOf(elem, 2*elem.length);
}
elem[usedsize] = val;
shifUp(usedsize);
}
private boolean isFull(){
if (usedsize == elem.length){
return true;
}
return false;
}
private void shifUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if (elem[child] > elem[parent]) {
swap(child, parent);
child = parent;
parent = (child-1)/2;
} else {
break;
}
}
}
删除：是将堆中的堆顶元素删除（即完全二叉树中的根结点），思路是先将根结点与最后一个结点交换，然后将计数器减1即可。
public int poll(){
int temp = elem[0];
swap(0, usedsize-1);
shiftdown(0, --usedsize);
return temp;
}下面有一些关于堆相关的题目
例1：
做这题我们需要知道堆的性质（大堆和小堆的概念），看题目可以知道这个是大堆为准，将数组构建成一个完全二叉树，对比每一棵子树是否满足根结点大于左右结点即可，答案选 A。
例2：
根据堆的删除需要将根结点与最后一个结点交换，计数器减1，然后再调整堆。调整需要对左右结点进行比较，直至堆符合堆的性质，答案选C。
常用接口
PriorityQueue的特性
PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的。
PriorityQueue默认是小堆；放入的元素必须能够比较大小，如果放入的对象是不能比较的就会抛出异常；也不能插入null对象，不然也会抛异常；没有容量限制可以插入任意个元素（内部会自动扩容）；插入和删除的时间复杂度为O(logN)；PriorityQueue底层使用了堆数据结构。
PriorityQueue常用接口
构造方法有无参构造、指定容量构造、采用集合构造。默认情况下PriorityQueue队列的是小堆，如果要创建一个大堆需要提供比较器。
PriorityQueue q = new PriorityQueue();PriorityQueue接口下的一些方法；
例：top-K问题：最大或最小的前k个数据。比如：世界前500强公司
面试题 17.14. 最小K个数 - 力扣（LeetCode）
如果是按照我们通用思维逻辑来说，可能都是将这些数据从大到小或从小到大排序，如果面临的是少个数据这个排序的方法可以使用，但面临很多数据时很明显效率就低了。我们现在换一种思考想这个问题，如果我们先将前k个数据构成一个大堆，然后再将数组剩下的数依次进行比较，如果比根结点小那就先删除根结点再插入数组，比根结点大说明并不是前k个最小的就跳过这次循环即可。
class IntCmp implements Comparator<Integer>{
@Override
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];
if (k <= 0){
return ret;
}
PriorityQueue<Integer> p = new PriorityQueue(new IntCmp());
for(int i = 0; i < k; i++){
p.offer(arr[i]);
}
for(int i = k; i < arr.length; i++){
int top = p.peek();
if (arr[i] < top){
p.poll();
p.offer(arr[i]);
}
}
for (int i = 0; i < k; i++){
ret[i] = p.poll();
}
return ret;
}
}
关于优先级队列的相关内容都在这啦，大家可以参考一下呢~