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

 登神长阶

 第六神装 优先级队列 PriorityQueue

第七神装  堆 Heap 

目录

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

📕1.概念

📖2.特点

📗二.认识堆（Heap） 

📘1.概念

📙2.特点 

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

📓1.堆的创建

📒2.建堆的时间复杂度

📃3.堆的插入和删除

📜3.1插入

📄 3.2删除

📰四.PriorityQueue接口介绍

🗞️1.基本使用

📑2.注意事项

🔖五.总结与反思

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

📕1.概念

        前面介绍过队列，在 Java 中，队列（Queue）是一种先进先出（FIFO）的数据结构，用于存储元素。队列在 java.util 包中有多种实现，如 LinkedList、ArrayDeque 和 PriorityQueue。只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

        Java中的优先级队列（PriorityQueue）是一种数据结构，它基于优先级的概念来确定元素的顺序。在优先级队列中，元素按照优先级被逐个访问和处理，具有较高优先级的元素会被优先处理。

📖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接口介绍

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线 程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。

🗞️1.基本使用

 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());
    }

注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器

 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("优先级队列不为空");
        }
    }

📑2.注意事项

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

🔖五.总结与反思

梦想只要能持久，就能成为现实。我们不就是生活在梦想中的吗？——丁尼生

        在学习Java中的PriorityQueue和堆这一主题时，我掌握了如何使用PriorityQueue类来实现堆的基本操作，包括插入和删除。这些操作对于解决许多实际问题都非常有用，尤其是在需要高效管理元素优先级的情况下。

        插入操作是向堆中添加新元素的过程，它的基本思路是保持堆的性质不变。通过PriorityQueue的add()或offer()方法，我们可以很方便地实现插入操作。插入操作的关键在于保证插入元素后，堆仍然满足堆的性质，这需要进行必要的上浮操作。这种自动维护堆性质的特性使得插入操作非常高效且便捷。

        删除操作是从堆中移除元素的过程，它也是一个关键的操作。通过PriorityQueue的remove()或poll()方法，我们可以轻松地实现删除操作。删除操作的核心在于保持堆的性质不变，这需要进行必要的下沉操作。下沉操作确保移动的元素与其子节点之间的关系满足堆的性质，从而维护堆的结构。

        过学习Java中的PriorityQueue和堆，我意识到了数据结构在解决实际问题中的重要性。掌握这些基本的数据结构和操作，可以为我在日后的编程工作中提供强大的支持。在未来，我计划通过更深入的学习和实践，进一步提升自己在数据结构和算法方面的能力，以应对更复杂的编程挑战。

        总的来说，学习Java中的PriorityQueue和堆是一次愉快且收获丰富的经历。我期待着将这些知识应用到实际项目中，并不断提升自己的编程技能。

🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀

以上，就是本期的全部内容啦，若有错误疏忽希望各位大佬及时指出💐

  制作不易，希望能对各位提供微小的帮助，可否留下你免费的赞呢🌸