登神长阶

 第六神装 优先级队列 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中，可以使用 <code>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.堆的创建

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

因此，会出现：

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

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

<code> 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

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

  代码要用到向下调整的代码：

<code>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插入

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

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

向上调整 

<code>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删除

注意：堆的删除一定删除的是堆顶元素。

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

 要用到向上调整 

<code>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.基本使用

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

}

}

常用的操作如下：

<code> 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和堆是一次愉快且收获丰富的经历。我期待着将这些知识应用到实际项目中，并不断提升自己的编程技能。

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

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

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