优先级队列（堆）详解

1、堆的概念

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
从堆的概念中不难看出，堆实际上是一个特殊的完全二叉树。必须满足的条件是：对于每一个根结点都小于它的孩子结点（小堆）或者每一个根节点都大于孩子结点（大堆）。
如下图：
在这里插入图片描述

2、堆的存储方式

堆是一颗完全二叉树，可以按照层序的规则采用顺序的方式进行存储。（对于非完全二叉树，在存储过程中会存储空结点，浪费空间）
将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：
如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

3、堆的基本操作

1、向下调整

在讲堆的建立之前，我们要了解一个非常重要的操作：向下调整。
我们以建小根堆为例，给定这样一个完全二叉树：
在这里插入图片描述
我们要把它变成一个小根堆，就要使用到向下调整的方法，对于小根堆我们要保证每一个根结点都小于它的叶子结点（如果有叶子结点）。步骤如下：

先从最初的根结点开始，记为parent结点，找到其左孩子结点（数组下标2*parent+1）。
判断有没有右孩子结点，如果存在找到左右孩子中最小的孩子，让child进行标记。
将parent与较小的孩子child比较，如果：parent小于较小的孩子child，调整结束。
否则：交换parent与较小的孩子child，交换完成之后，parent中大的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整，即parent = child，child = parent*2+1。然后重复这个过程。直到parent超出数组下标。
下图是向下调整的过程：
向下调整的过程也是对于这颗树进行迭代比较而实现的。仔细思考一下，我们发现向下调整的过程其实只影响改变了一条路径，每次遇到孩子结点都有两种情况：1、parent结点不需要和child结点互换，调整直接结束。2、parent结点需要和child结点互换，将child结点作为parent结点继续调整。不需要调整的部分原来就是符合堆的定义，我们只是在这条路径上将最顶部的元素下调至相应位置，这才是parent可以一条路走到黑的根本原因。接下来，我们来看代码（十分巧妙）：

  public void shiftDown(int[] array, int parent) {
        int child = 2*parent+1;//左孩子结点
        while(child<array.length) {
            if(child+1< array.length&&array[child]<array[child+1]) {
            //先判断右孩子存不存在，再找出两个孩子中的较大孩子
                child+=1;//child指向较大的孩子结点
            }
            if(array[parent]>array[child]) {//比最大的孩子还大，向下调整
                swap(array,parent,child);
            }else{
                break;
            }
            parent = child;//继续向下调整
            child = 2*parent+1;
        }

注意：在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。

2、堆的创建

对于一个普通序列：根节点的左右子树不满足堆的特性，我们又该如何调整呢？
答案仍然是利用向下调整，只不过我们要从下向上考虑。步骤如下：

从后向前，找到第一个不为叶子结点的结点，记为root。
从这个根结点向前遍历数组（root–），每遇到一个结点就向下调整一次，直到走完数组（root<0）。
直接上代码：

  public static void createHeap(int[] array) {
        int root = (array.length-1-1)/2;//根据孩子结点求根结点
        for(;root>=0;root--) {
            shiftDown(array,root);
        }
    }

3、堆的插入

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

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

这时，我们所做的实际上是一种向上调整。仍然以小根堆为例，下面是代码实现：

public static void shiftUp(int[] array,int child) {
        int parent = (child-1)/2;
        while(child>0) {
            if(array[parent]>array[child]) {
                swap(array,parent,child);
            }else{
                break;
            }
            child = parent;
            parent = (child-1)/2;
        }
    }

比较向上调整与向下调整：
1、向上调整是通过child结点去找parent结点，而向下调整是通过parent结点去找child结点。
2、建堆的时候使用向下调整，而不使用向上调整。因为向下调整操作的复杂度较低。

4、堆的删除

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

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

4、优先级队列模拟实现

前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，
在这种情况下，数据结构应该提供两个最基本的操作：一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。
我们接下来使用堆的操作模拟实现优先级队列，直接上代码：

import java.util.Arrays;

public class PriorityQueue {
    public int[] array;
    public int usedSize;
    public static final int default_Capacity = 10;//默认容量

    public PriorityQueue() {
        this.usedSize = 0;
        this.array = new int[default_Capacity];
    }

    /**
     *
     * @param array
     */
    public void createHeap(int[] array) {
        int parent = (array.length-2)/2;
        for(;parent>=0;parent--) {
            shiftDown(parent,usedSize);
        }
    }

    public static void swap (int[] array,int parent,int child) {
        int tmp = array[parent];
        array[parent] = array[child];
        array[child] = tmp;
    }
    /**
     *
     * @param parent 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int parent,int len) {
        int child = 2*parent+1;
        while(child<len) {
            if(child+1<len&&array[child]<array[child+1]) {
                child+=1;//child指向较大的孩子结点
            }
            if(array[parent]>array[child]) {
                swap(array,parent,child);
            }else{
                break;
            }
            parent = child;
            child = 2*parent+1;
        }
    }


    /**
     * 入队：仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
        if(isFull()) {
            array = Arrays.copyOf(array,2*array.length);
        }
        array[usedSize] = val;
        usedSize++;
        shiftUp(usedSize-1);
    }

    private void shiftUp(int child) {
        int parent = (child-1)/2;
        while(child>0) {
            if(array[parent]>array[child]) {
                swap(array,parent,child);
            }else{
                break;
            }
            child = parent;
            parent = (child-1)/2;
        }
    }

    public boolean isFull() {
        return usedSize == array.length;
    }

    /**
     * 出队【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public int pollHeap() {
        int tmp = array[0];
        swap(array,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
        return tmp;
    }

    public boolean isEmpty() {
        return usedSize==0;
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {
        return array[0];
    }
}

5、PriorityQueue接口介绍

三种构造器：

PriorityQueue() 创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列，注意：
initialCapacity不能小于1，否则会抛IllegalArgumentException异常
PriorityQueue(Collection<?extends E> c) 用一个集合来创建优先级队列

常用方法：

booleanoffer(E e)插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度为O（log2N），注意：空间不够时候会进行扩容
E peek() 获取优先级最高的元素，如果优先级队列为空，返回null
E poll() 移除优先级最高的元素并返回，如果优先级队列为空，返回null
int size() 获取有效元素的个数
void clear() 清空队列
boolean isEmpty() 检测优先级队列是否为空，空返回true

6、堆排序

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

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

   public void heapSort() {
        int end = usedSize-1;
        while (end > 0) {
            swap(0,end);
            siftDown(0,end-1);
            end--;
        }

7、Top-k问题（堆排序的应用）

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
基本思路如下：

用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

//使用比较器创建小根堆
class LessIntComp implements Comparator<Integer> { 
	@Override
	public int compare(Integer o1, Integer o2) { return o1 - o2; }
 }
//使用比较器创建大根堆
class GreaterIntComp implements Comparator<Integer>{ 
	@Override
	public int compare(Integer o1, Integer o2) { return o2 - o1; 
	} 
}
public class TestDemo<E> { //求最小的K个数，通过比较器创建大根堆
	public static int[] smallestK(int[] array, int k) { 
	if(k <= 0) { 
		return new int[k]; 
	}
	GreaterIntComp greaterCmp = new GreaterIntComp(); 
	PriorityQueue<Integer> maxHeap = new PriorityQueue<>(greaterCmp); 
	//先将前K个元素，创建大根堆 
	for(int i = 0; i < k; i++) {
		maxHeap.offer(array[i]); 
	}
	//从第K+1个元素开始，每次和堆顶元素比较 
	for (int i = k; i < array.length; i++) { 
	int top = maxHeap.peek(); 
	if(array[i] < top) {
		maxHeap.poll();
		maxHeap.offer(array[i]); 
		} 
	}
	//取出前K个
	int[] ret = new int[k]; 
	for (int i = 0; i < k; i++) { 
		int val = maxHeap.poll(); 
		ret[i] = val;
	}
	return ret; 
}