优先级队列（堆）

概念
模拟实现
- 堆的概念
- 堆的存储方式
- 堆的创建
- - 向下调整
  - 堆的创建
  - 建堆的时间复杂度
- 堆的插入和删除
- - 堆的插入
  - 堆的删除
- 用堆模拟实现优先级队列
常用接口
- PriorityQueue的特性
- PriorityQueue常用接口介绍
- - 构造方法
  - 插入/删除/获取优先级最高的元素
- PriorityQueue 部分源码解析
- - 构造方法
  - - public PriorityQueue()
    - PriorityQueue(int initialCapacity)
    - public PriorityQueue(Comparator<? super E> comparator)
    - public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
    - public PriorityQueue(Collection<? extends E> c)
  - public boolean add(E e)和public boolean offer(E e)
  - public E peek()
  - private int indexOf(Object o)
  - public E poll()
  - private void siftUp(int k, E x)
  - - private void siftUpUsingComparator(int k, E x)
    - private void siftUpComparable(int k, E x)
  - private void siftDown(int k, E x)
Topk问题

概念

队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。

在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

模拟实现

JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。

堆的概念

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

简单来说就是孩子节点的值一定大于或小于父亲节点的值
孩子节点都大于父亲节点则是小根堆反之则是大根堆
在这里插入图片描述
堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

在这里插入图片描述

堆的存储方式

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，

注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。

将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：

如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

堆的创建

向下调整

对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆呢？
在这里插入图片描述

仔细观察上图后发现：根节点的左右子树已经完全满足堆的性质，因此只需将根节点向下调整好即可

向下过程(以小堆为例)：

让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子因为是完全二叉树)
如果parent的左孩子存在，即:child < size，进行以下操作，直到parent的左孩子不存在
parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标记孩子的下标
将parent与较小的孩子child比较如果parent小于较小的孩子child 说明此时已经是小根堆不调整否则交换parent和较小的孩子child 交换完成后 parent可能大于他的孩子的孩子此时还需要继续调整
使parent = child child 2 * parent + 1 然后继续过程2 知道到达树的底部也就是parent 不存在孩子节点的时候

public void shiftDown(int[] array, int parent) {
        // child先标记parent的左孩子，因为parent可能右左没有右
        int child = 2 * parent + 1;
        int size = array.length;
        while (child < size) {
            // 如果右孩子存在，找到左右孩子中较小的孩子,用child进行标记
            if (child + 1 < size && array[child + 1] < array[child]) {
                child += 1;
            }
            // 如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了
            if (array[parent] <= array[child]) {
                break;
            } else {
                // 将双亲与较小的孩子交换
                int t = array[parent];
                array[parent] = array[child];
                array[child] = t;
                // parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
                parent = child;
                child = parent * 2 + 1;
            }
        }
    }

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

时间复杂度分析：
最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为在这里插入图片描述

堆的创建

那对于普通的序列{ 1,5,3,8,7,6 }构建为大根堆，即根节点的左右子树不满足堆的特性，又该如何调整呢？

向下调整的前提条件是parent的左右子树都是堆 所以我们只需要从最后一个非叶子节点开始往前一直到根节点每遇到一个节点就向下调整这样就可以保证每次调整的时候他的左子树和右子树都是堆

public static void createHeap(int[] array) {
        // 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
        int root = ((array.length-1-1)>>1);
        //array.lenth-1是最后一个节点的下标
        //再-1 然后/2的目的是找到他的父亲节点 
        //最后一个节点的父亲节点就是最后一个非叶子节点的节点 往前知道调整完0下标
        for (; root >= 0; root--) {
            shiftDown(array, root);
        }
    }

建堆的时间复杂度

在这里插入图片描述

堆的插入和删除

堆的插入

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

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

    public void shiftUp(int child) {
        // 找到child的双亲
        int parent = (child - 1) / 2;
        while (child > 0) {
        // 如果双亲比孩子大，parent满足堆的性质，调整结束
            if (array[parent] > array[child]) {
                break;
            }
            else{
                // 将双亲与孩子节点进行交换
                int t = array[parent];
                array[parent] = array[child];
                array[child] = t;
                // 小的元素向下移动，可能到值子树不满足对的性质，因此需要继续向上调增
                child = parent;
                parent = (child - 1) / 2;
            }
        }
    }

堆的删除

注意：堆的删除一定删除的是堆顶元素因为实现的是一个队列

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

用堆模拟实现优先级队列

public class Heap {
    public int[] elem;
    public int usedSize;

    public Heap() {
        this.elem = new int[10];
    }

    //创建一个大根堆
    public void createHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
        //从最后一个根节点开始
        //usedSize - 1 是最后一个节点的下标
        //((usedSize - 1) - 1) / 2是这个节点的父节点 也就是最后一个父节点
        //从这个节点开始对每棵树进行调整
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent --){
            shiftDown(parent,usedSize);
        }
    }

    /**
     * @param parent 每棵子树的根节点
     * @param len    代表每棵子树的结束位置
     */
    //
    private void shiftDown(int parent, int len) {
        int child = 2 * parent + 1;
        //左孩子节点的下标
        while (child < len) {
            //if的目的是找出左右孩子中较大的那个孩子的下标
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                //child + 1 < len 的目的是保证右节点也在下标的范围内 防止数组越界
                //elem[child] < elem[child + 1]
                child = child + 1;
            }
            //if的目的是判断较大的那个孩子节点有没有父节点大
            if (elem[child] > elem[parent]) {
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                //将其中较大的放在根位置
                parent = child;
                child = 2 * parent + 1;
                //此时这棵树调整完整 在调整下一颗；
            } else {
                break;
                //此时就是大根堆
            }
        }
    }

    //向上调整
    public void shiftUp(int child){
        int parent = (child - 1) / 2;
        while (child > 0){
            if(elem[child] > elem[parent]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }

    public void push(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem,2 * elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
        shiftUp(usedSize - 1);
        //每添加一个元素 就向上调整一次 保证还是大根堆；
    }

    private boolean isFull(){
        return this.usedSize == elem.length;
    }

    public int poll(){
        if(empty()){
            throw new HeapEmptyException("优先级队列为空");
        }
        int temp = elem[0];
        elem[0] = elem[usedSize - 1];
        elem[usedSize - 1] =temp;
        usedSize --;
        shiftDown(0,usedSize);
        return temp;
        /**
         * 逻辑为：
         * poll方法的功能为弹出下标为0的元素
         * 但是我们是优先级队列 弹出第一个元素整棵树就不是堆
         * 我们就把第一个元素和最后一个元素交换 然后使usedSize-- 来删除第一个元素
         * 返回第一个元素 在向下调整根节点对应的树
         *
         */

    }

    private boolean empty(){
        return this.usedSize == 0;
    }

    public int peek(){
        if(empty()){
            throw new HeapEmptyException("优先级队列为空");
        }
        return elem[0];
    }
}

常用接口

PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。
在这里插入图片描述
注意事项：

使用时必须导入PriorityQueue所在的包
PriorityQueue中放置的元素必须要能够比较大小 因为向上或者向下调整时要进行元素的大小比较，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
. 不能插入null对象，否则会抛出NullPointerException
没有容量限制，可以插入任意多个元素，其内部可以自动扩容
插入元素和删除元素的时间复杂度都是O(logN)
PriorityQueue底层使用了堆数据结构
PriorityQueue默认情况下是小堆-–即每次获取到的元素都是最小的元素

PriorityQueue常用接口介绍

构造方法

常用的三种
在这里插入图片描述
但是PriorityQueue队列是小堆，如果我们需要大堆就需要我们提供一个比较器

插入/删除/获取优先级最高的元素

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

PriorityQueue 部分源码解析

构造方法

在这里插入图片描述

public PriorityQueue()

在这里插入图片描述
**这里看到它调用了另一个构造方法 **

第一个参数是优先级队列的默认容量
在这里插入图片描述
第二个参数是一个比较器默认为null

PriorityQueue(int initialCapacity)

在这里插入图片描述
这个构造方法需要一个容量来代替他的默认容量我们可以指定优先级队列的初始大小

但是还是调用了另一个构造方法

public PriorityQueue(Comparator<? super E> comparator)

在这里插入图片描述
这个构造方法我们可以传入一个比较器容量是默认容量

但是还是调用了另一个构造方法

public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

最关键的一个构造方法我们发现其他构造方法都是间接调用了这个构造方法需要一个参数和比较器

在这里插入图片描述

public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        //如果容量小于1 则抛出异常
        this.queue = new Object[initialCapacity];
        // 初始化优先级队列
        this.comparator = comparator;
        // 比较器为我们传入的比较器
    }

public PriorityQueue(Collection<? extends E> c)

还可以传入一个集合来将其中的值赋值给优先级队列

在这里插入图片描述
大体逻辑就是判断这个集合是否为if中的两个集合如果是则把数据和比较器都传给优先级队列如果不是即else 则比较器赋值null 把值传递给优先级队列

public boolean add(E e)和public boolean offer(E e)

这两个方法放在一起是因为add方法实际上调用了offer方法

在这里插入图片描述

offer方法
在这里插入图片描述
和我们模拟实现的优先级队列方法基本相同

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        //传入null抛出空指针异常
        modCount++;
        int i = size;
        //获取优先级队列元素个数
        if (i >= queue.length)
            grow(i + 1);
        //扩容方法
        //如果空间不足则需要扩容
        size = i + 1;
        //元素个数+1
        if (i == 0)
            queue[0] = e;
        //如果是第一个元素 则直接放在数组里
        else
            siftUp(i, e);
        //如果不是则需要向上调整 
        return true;
    }

public E peek()

在这里插入图片描述
直接返回队头元素如果队列为空则返回null

private int indexOf(Object o)

查找对应元素的下标
在这里插入图片描述
找到返回下标找不到返回-1

public E poll()

弹出队头元素
在这里插入图片描述

public E poll() {
    if (size == 0)
        return null;
    //队列中没有元素 返回null
    int s = --size;
    //队列元素--
    modCount++;
    E result = (E) queue[0];
    //保存队头元素 以返回
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        //如果此时队列中还有元素
        siftDown(0, x);
        //向下调整 其中包含了将根节点放到队尾的操作
    return result;
    //返回根节点
}

private void siftUp(int k, E x)

向上调整方法
private修饰说明我们不能再类外对 siftUp方法进行调用

在这里插入图片描述
我们可以看到有一个if语句判断是否有比较器

private void siftUpUsingComparator(int k, E x)

如果if为真说明我们有一个比较器
在这里插入图片描述

private void siftUpUsingComparator(int k, E x) {
        //x 为孩子节点
        //k 为孩子节点的下标
        //向上调整 从根节点开始调整
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            //获取孩子节点对应的根节点的下标
            Object e = queue[parent];
            //获取父亲节点下标的元素
            if (comparator.compare(x, (E) e) >= 0)
                //比较器比较 如果为真说明已经满足堆的要求
                break;
            queue[k] = e;
            //父亲节点的值给了孩子节点
            k = parent;
            //否则 下一个孩子节点为这个父亲节点
        }
        queue[k] = x;
        //第一次只把父亲节点的值给了孩子节点 孩子节点并没有赋值父亲节点 在这里赋值
    }

private void siftUpComparable(int k, E x)

if为假说明我们的比较器为null
在这里插入图片描述

private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        //看看x对应的类是否实现了comparable接口
        //如果没有比较器 且该类没有实现comparable接口 程序报错
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                //如果程序执行到这里 说明已经实现了comparable接口
                //此时该类必须重写compareTo方法
                //这里调用类中的compareTo方法来判断大小
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;

        //其余逻辑和上个方法一模一样
    }

private void siftDown(int k, E x)

这个方法和siftUp方法几乎一模一样
在这里插入图片描述
也是区分了有无比较器
向下调整的内部逻辑和我们实现的也基本一致

Topk问题

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

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

**例如我们要一组数据的前k个最小的数我们就创建一个有k个元素的大根堆对于那组数据从第k + 1个数开始遍历如果遍历过程中遇到小于堆顶元素的元素此时就把这个元素放在堆顶然后对堆进行向下调整使堆顶总是这个堆中最大的元素直到遍历结束 **

代码实现

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] temp = new int[k];
        if(k == 0){
            return temp;
        }
        PriorityQueue<Integer> Heap = new PriorityQueue<>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });

        for(int i = 0;i < k; i++){
            Heap.offer(arr[i]);
        }
        for(int i = k; i < arr.length; i++){
            if(arr[i] < Heap.peek()){
                Heap.poll();
                Heap.offer(arr[i]);
            }
        }
         for(int i = 0;i < k; i++){
            temp[i] = Heap.poll();
        }
        return temp;
    }
    
}