PriorityQueue优先级队列

前言

优先级队列就是在堆的基础上进行改造，那么什么是堆，又什么是优先级队列呢？

我们一起来看看吧！

前言

一、堆

（一）堆的创建

（二）堆的插入

（三）堆的删除

（四）模拟实现堆

二、优先级队列

（一）常用方法：

（二）常考点

结语

一、堆

堆就是堆中某个节点的值总是不大于或不小于其父节点的值。

堆总是完全二叉树。

Java底层的堆是顺序表，按照层序遍历的规则存储数据。

堆分为小根堆和大根堆。

1.小根堆（又名最小堆）：

就是堆中某个节点的值总是不小于其父节点的值。

例如：

2.大根堆（又名最大堆）：

就是堆中某个节点的值总是不大于其父节点的值。

例如：

以创建最小堆为例，给出的数据顺序是： 5、3、6、7、4、2.

（一）堆的创建

首先，根据给出的数据顺序，创建如下二叉树：

从最后一个叶子节点开始调整（向上调整）：

时间复杂度是：O（n）

（二）堆的插入

假设要插入数据0：

如果在插入数据时，堆满扩容；调整为向上调整。

时间复杂度是：O(log n)

（三）堆的删除

堆的删除一定删除的是堆顶元素。

时间复杂度是：O(log n)

（四）模拟实现堆

代码：

import java.util.Arrays;
import java.util.Comparator;

class PriorityException extends RuntimeException{
    public PriorityException(String s){
        super(s);
    }
}


public class MyPriortyQueue implements Comparator<Integer> {
    public int[] elem;
    public int usedSize;

    public MyPriortyQueue(int k) {
        elem = new int[k];
    }

    public MyPriortyQueue() {
        elem = new int[11];
    }

    @Override
    public int compare(Integer o1,Integer o2) {
        return o2.compareTo(o1);
    }

    /**
     * 建堆
     */
    public void createHeap(int[] array) {
        for(int i = 0; i < array.length; i++){
            elem[i] = array[i];
            usedSize++;
        }
        for(int i = (usedSize-1-1)/2; i >= 0; i--){
            shiftDown(i,usedSize-1);
        }
    }

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


    /**
     * 入队：仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
        if(isEmpty()){
            elem[0] = val;
        }else{
            elem[usedSize] = val;
        }
        usedSize++;
        shiftUp(usedSize-1);
    }
    /**
     * 向上调整
     * 默认除了需要调整的地方外，其余都是已经调整好了的
     */
    private void shiftUp(int child) {
        int parent = (child-1)/2;
        while(child > 0){
            if(compare(elem[parent],elem[child])>0){
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }

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

    /**
     * 出队【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public void pollHeap() throws PriorityException{
        if(isEmpty()){
            throw new PriorityException("pollHeap::队列无元素，删除失败");
        }
        elem[0] = elem[usedSize-1];
        usedSize--;
        shiftDown(0, usedSize-1);
    }

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

    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() throws PriorityException{
        if(isEmpty()){
            throw new PriorityException("peekEmpty::队列无元素，获取失败");
        }
        return elem[0];
    }

    public static void main(String[] args) {
        MyPriortyQueue p = new MyPriortyQueue();
        int[] arr = {2,4,2,5,7,9,5,3};
        p.createHeap(arr);
        System.out.println("+=========创建一个堆========+");
        System.out.println(Arrays.toString(p.elem));
        p.push(10);
        System.out.println("+=========入一个值========+");
        System.out.println(Arrays.toString(p.elem));
        System.out.println("+=========输出堆顶========+");
        System.out.println(p.peekHeap());
        p.pollHeap();
        System.out.println("+=========删除堆顶=======+");
        System.out.println(Arrays.toString(p.elem));
    }
}

代码链接在GitHub：堆_练习模拟实现2 · Yjun6/DataStructrue@98faae5 (github.com)

二、优先级队列

PriorityQueue<Integer> p = new PriorityQueue<>();

（一）常用方法：

boolean offer(E e)	插入元素e,成功插入返回true;会自动扩容；如果e为空，会抛出异常
E peek()	获取优先级队列最高的元素；若队列为空，返回null
E poll()	移除优先级队列最高的元素；若队列为空，返回null
int size()	获取有效元素个数
void clear()	清空
boolean isEmpty()	判断是否为空

关于创建优先级队列的方法：

PriorityQueue()	初始容量为11，默认无比较器
PriorityQueue(int k)	初始容量为k，k>0
PriorityQueue(Collection<? extend E> c)	用一个集合创建优先级队列

优先级队列扩容说明：

如果容量小于64，按照2倍扩容；
如果容量大于等于64，按照1.5倍扩容；
如果容量超过 MAX_ARRAY_SIZE，按照 MAX_ARRAY_SIZE 进行扩容。

（二）常考点

求前k个最大值、前k个最小值、第k个最大值、第k个最小值……

面试题 17.14. 最小K个数 - 力扣（Leetcode）

代码：

class Solution {
    public int[] smallestK(int[] arr, int k) {
        if(arr == null || k == 0) return new int[k];
        Comp comp = new Comp();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(comp);//求大根堆
        for(int i = 0; i < k; i++){
            priorityQueue.offer(arr[i]);
        }
        for(int i = k; i < arr.length; i++){
            if(arr[i] < priorityQueue.peek()){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        int[] str = new int[priorityQueue.size()];
        for(int i = 0; i < str.length; i++){
            str[i] = priorityQueue.poll();
        }
        return str;
    }
}


class Comp implements Comparator<Integer> {
    @Override
    public int compare(Integer a, Integer b){
        return b.compareTo(a);
    }
}