Java 【数据结构】 优先级队列（PriorityQueue）和堆（Heap）【神装】

 登神长阶

 第六神装 优先级队列 PriorityQueue

第七神装  堆 Heap 

目录

📔一.认识优先级队列（PriorityQueue）

📕1.概念

📖2.特点

📗二.认识堆（Heap） 

📘1.概念

📙2.特点 

📚三.优先级队列的模拟实现

📓1.堆的创建

📒2.建堆的时间复杂度

📃3.堆的插入和删除

📜3.1插入

📄 3.2删除

📰四.PriorityQueue接口介绍

🗞️1.基本使用

📑2.注意事项

🔖五.总结与反思

📔一.认识优先级队列（PriorityQueue）

📕1.概念

📖2.特点

• 元素的排序： 优先级队列中的元素根据其优先级进行排序。具体来说，元素必须是可比较的，或者队列需要根据给定的比较器来确定优先级。

• 内部实现： Java中的优先级队列通常使用堆（heap）来实现。堆是一种特殊的树形数据结构，这也是本篇博客把二者放在一起的原因，下文会做详细介绍。

• 插入和删除操作： 优先级队列支持插入和删除操作。插入操作将元素插入到队列中，并根据其优先级进行调整；删除操作移除并返回队列中优先级最高的元素。

• 访问操作： 优先级队列通常支持访问具有最高优先级的元素，但不一定支持随机访问其他元素。在Java中，可以使用 peek() 方法来访问队首元素，该方法返回队列中优先级最高的元素但不移除它。

• 线程安全性： Java中的优先级队列实现通常不是线程安全的。如果需要在多线程环境中使用优先级队列，可以考虑使用 PriorityBlockingQueue 类，它是 BlockingQueue 接口的一个实现，提供了线程安全的优先级队列功能。

综上所述，Java中的优先级队列是一种重要的数据结构，适用于需要按照优先级处理元素的场景，例如任务调度、事件处理等。

📗二.认识堆（Heap） 

📘1.概念

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

📙2.特点 

• 完全二叉树结构： 堆通常是一棵完全二叉树，即除了最底层，其他层都是满的，并且最底层从左向右填充。

• 最大堆和最小堆： 堆可以分为最大堆（Max Heap）和最小堆（Min Heap）两种类型。

  • 在最大堆中，父节点的值大于等于其子节点的值，因此根节点是最大值。
  • 在最小堆中，父节点的值小于等于其子节点的值，因此根节点是最小值。

• 堆的性质： 堆的一个重要性质是堆中的每个节点都满足堆的性质，即父节点的值要么大于等于/小于等于其子节点的值，这取决于是最大堆还是最小堆。

• 插入操作： 向堆中插入元素时，通常会将元素放置在堆的末尾，然后通过上移操作（向上调整）将元素移到合适的位置，以满足堆的性质。

• 删除操作： 从堆中删除元素时，通常会删除根节点，并将堆的最后一个元素移动到根节点位置，然后通过下移操作（向下调整）将元素移到合适的位置，以满足堆的性质。

• 堆的实现： 在Java中，堆通常通过数组来实现。数组的每个元素对应堆中的一个节点，通过索引可以方便地找到节点的父节点和子节点。

• 应用： 堆在计算机科学中有许多重要的应用，例如优先级队列、堆排序、最小（大）k个元素问题等。其中，优先级队列是最常见的应用之一，可以使用堆来实现高效的优先级队列。

总之，堆是一种重要的数据结构，具有高效的插入、删除和访问操作，适用于需要快速找到最大值或最小值的场景。

📚三.优先级队列的模拟实现

📓1.堆的创建

        根据初步认识，我们知道堆是一颗完全二叉树：

因此，会出现：

根节点的左右子树已经完全满足堆的性质，此时只需要将根节点向下调整即可，以下为例：

 基本思路为向下调整，代码如下：

 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 的左子树和右子树已经是堆了才可以向下调整。

时间复杂度分析： 最坏的情况 即图示的情况， 从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为log2N

在实际应用之中对于普通的序列，即根节点的左右子树不满足堆的特性，调整方法逻辑如下  代码要用到向下调整的代码：

public static void createHeap(int[] array) {
    // 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
    int root = ((array.length-2)>>1);
    for (; root >= 0; root--) {
        shiftDown(array, root);
    }
}

📒2.建堆的时间复杂度

        因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：此处要用到错位相减的思想：

 因此：建堆的时间复杂度为O(N)。

📃3.堆的插入和删除

📜3.1插入

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

   

向上调整 

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) / 1;
            }
        }
    }

📄 3.2删除

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

 要用到向上调整 

public class MyPriorityQueue {
        // 演示作用，不再考虑扩容部分的代码
        private int[] array = new int[100];
        private int size = 0;
        public void offer(int e) {
            array[size++] = e;
            shiftUp(size - 1);
        }
        public int poll() {
            int oldValue = array[0];
            array[0] = array[--size];
            shiftDown(0);
            return oldValue;
        }
        public int peek() {
            return array[0];
        }
    }

📰四.PriorityQueue接口介绍

 static void TestPriorityQueue(){
    // 创建一个空的优先级队列，底层默认容量是11
        PriorityQueue<Integer> q1 = new PriorityQueue<>();
    // 创建一个空的优先级队列，底层的容量为initialCapacity
        PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
        ArrayList<Integer> list = new ArrayList<>();
        list.add(4);
        list.add(3);
        list.add(2);
        list.add(1);
    // 用ArrayList对象来构造一个优先级队列的对象
    // q3中已经包含了三个元素
        PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
        System.out.println(q3.size());
        System.out.println(q3.peek());
    }

 public class TestPriorityQueue {
        public static void main(String[] args) {
            PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
            p.offer(4);
            p.offer(3);
            p.offer(2);
            p.offer(1);
            p.offer(5);
            System.out.println(p.peek());
        }
    }

  static void TestPriorityQueue2(){
        int[] arr = {4,1,9,2,8,0,7,3,6,5};
    // 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
    // 否则在插入时需要不多的扩容
    // 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
        PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
        for (int e: arr) {
            q.offer(e);
        }
        System.out.println(q.size()); // 打印优先级队列中有效元素个数
        System.out.println(q.peek()); // 获取优先级最高的元素
    // 从优先级队列中删除两个元素之和，再次获取优先级最高的元素
        q.poll();
        q.poll();
        System.out.println(q.size()); // 打印优先级队列中有效元素个数
        System.out.println(q.peek()); // 获取优先级最高的元素
        q.offer(0);
        System.out.println(q.peek()); // 获取优先级最高的元素
    // 将优先级队列中的有效元素删除掉，检测其是否为空
        q.clear();
        if(q.isEmpty()){
            System.out.println("优先级队列已经为空!!!");
        }
        else{
            System.out.println("优先级队列不为空");
        }
    }