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 {
    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+11])>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 p = new PriorityQueue<>();

（一）常用方法：

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

优先级队列扩容说明：

• 如果容量小于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 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 {
    @Override
    public int compare(Integer a, Integer b){
        return b.compareTo(a);
    }
}

---

结语

小编能力有限，欢迎大家指出错误哦~

这篇博客如果对你有帮助，给博主一个免费的点赞以示鼓励，欢迎各位🔎点赞👍评论收藏⭐，谢谢！！！