移动互联网的应用论文_东莞市手机网站建设怎么样_广州推广优化_网站注册地址查询

1. 概念

队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列。优先级队列中的元素按照优先级进行排序，具有更高优先级的元素会在队列中被优先处理。

2. 优先级队列的模拟实现

2.1 堆的概念

PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。

• 完全二叉树：堆是完全二叉树，通常用数组表示。
• 堆性质：
  • 最大堆：每个父节点的值大于或等于其子节点的值，根节点是最大值。
  • 最小堆：每个父节点的值小于或等于其子节点的值，根节点是最小值。

2.2 堆的存储方式

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，

注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。

• 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
• 若2i+1<n，左孩子序号：2i+1，否则无左孩子
• 若2i+2<n，右孩子序号：2i+2，否则无右孩子

    70/  \56   30/ \   / \
10  15 25 10
Array: [70, 56, 30, 10, 15, 25, 10]

2.3 堆的创建

2.3.1 堆的向下调整

假设我们有以下一个二叉树:

    10/  \56   30/ \   / 
10  15 25 

数组表示为: [10, 56, 30, 10, 15, 25]

根节点的左右子树已经完全满足堆的性质，现在·需要将根节点进行向下调整操作来维护堆的性质。

向下调整的过程如下:

1. 由于 10 不满足最大堆的性质,需要向下调整。
2. 将 10 与它的左右子节点中较大的一个(56)交换。
3. 继续向下调整,直到满足最大堆的性质。

调整后的堆结构如下:

    56/  \15   30/ \   / 
10  10 25 

数组表示为: [56, 15, 30, 10, 10, 25]

注意：在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。

时间复杂度分析：

最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为$O(logn)$

2.3.2 堆的创建

1. 将输入数组中的元素按照从上到下、从左到右的顺序存储在数组中。
2. 从最后一个非叶子节点开始,对每个节点进行向下调整,使其满足最大堆或最小堆的性质。

我们以 最大堆 为例，按照步骤进行堆的创建，给出调整过程以及对应的图示。

输入数组：1, 5, 3, 8, 7, 6

步骤 1：将数组元素按照从上到下、从左到右的顺序存储在完全二叉树中。

初始的完全二叉树表示如下（数组索引从 0 开始）：

          1/    \5      3/ \    /8   7  6

步骤 2：从最后一个非叶子节点开始向下调整

最后一个非叶子节点的索引为：(n / 2) - 1，其中 n 为数组长度。
对于数组 [1, 5, 3, 8, 7, 6]，n = 6，所以最后一个非叶子节点为索引 2，对应值为 3。

调整过程

1. 从索引 2 开始调整（值为 3）

比较当前节点与其子节点，发现 6 > 3，需要交换。

          1/    \5      6/ \    /8   7  3

2. 调整索引 1（值为 5）

比较当前节点与其子节点，发现 8 > 5，需要交换。

          1/    \8      6/ \    /5   7  3

继续向下调整索引 3（值为 5）：
当前节点 5 没有子节点，无需调整。

3. 调整索引 0（值为 1）

比较当前节点与其子节点，发现 8 > 1，需要交换。

          8/    \1      6/ \    /5   7  3

继续向下调整索引 1（值为 1）：

比较当前节点与其子节点，发现 7 > 1，需要交换。

          8/    \7      6/ \    /5   1  3

继续向下调整索引 4（值为 1）：
当前节点 1 没有子节点，无需调整。

这种创建方式的时间复杂度为 O(n),比逐个插入元素的方式 O(n log n) 更加高效。

2.4 堆的插入与删除

2.4.1 堆的插入

1. 先将元素放到底层空间中，即最后一个孩子之后，
2. 插入之后如果堆的性质遭到破坏，将新插入的节点顺着其双亲往上调整到适当位置即可

堆的插入操作是向堆中添加一个新元素，并调整堆的结构以保持堆的性质（最大堆或最小堆）。我们以 最大堆 为例，演示插入的过程。

假设初始最大堆如下：

          8/    \7      6/ \    /5   1  3

插入新元素

假设我们要插入新元素 9。

步骤 1：将新元素插入到堆的最后一个位置

          8/    \7      6/ \    / \5   1  3   9

步骤 2：向上调整（Heapify Up）

从插入的节点开始，逐层向上调整，以满足最大堆的性质。

1. 当前节点为索引 6（值为 9），其父节点为索引 2（值为 6）。
   比较 9 > 6，需要交换。

          8/    \7      9/ \    / \5   1  3   6
   

2. 当前节点为索引 2（值为 9），其父节点为索引 0（值为 8）。
   比较 9 > 8，需要交换。

          9/    \8      7/ \    / \5   1  3   6
   

3. 当前节点为索引 0（值为 9），已经是根节点，无需继续调整。

2.4.2 堆的删除

堆的删除操作一般是指删除堆顶元素（最大堆中删除最大值或最小堆中删除最小值），并调整堆的结构以保持堆的性质。

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

我们以 最大堆 为例，演示删除堆顶元素的过程。

假设初始最大堆如下：

          9/    \8      7/ \    / \5   1  3   6

删除堆顶元素（最大值）

步骤 1：将堆顶元素（9）删除，并用最后一个元素代替堆顶

• 删除堆顶元素 9。
• 将最后一个元素 6 移到堆顶。

          6/    \8      7/ \    /5   1  3

步骤 2：向下调整（Heapify Down）

从新的堆顶开始，逐层向下调整，以满足最大堆的性质。

比较 6 与其子节点，发现 8 > 6，需要交换。

       8/    \6      7/ \    /5   1  3

比较 6 与其子节点，发现 6 > 5 和 6 > 1，无需交换。调整结束。

2.5 堆的模拟实现

package myDataStructure.Heap;import java.util.Arrays;
import java.util.NoSuchElementException;/*** @Author: Author* @CreateTime: 2025-03-23* @Description:*/
public class MyMaxHeap {private int[] heap; // 用于存储堆的数组private int size;   // 当前堆的大小// 构造函数public MyMaxHeap() {// 初始化堆的容量和数组heap=new int[10];}// 辅助交换方法private void swap(int i,int j){int temp=heap[i];heap[i]=heap[j];heap[j]=temp;}// 插入元素到堆中public void insert(int value) {expandCapacity();size++;// 插入操作heap[size-1]=value;heapifyUp(size-1);}// 删除堆顶元素（最大值）public int removeMax() {if (size==0) {throw new NoSuchElementException("Heap is empty, no maximum element available.");}int removedValue=heap[0];swap(0,size-1);heap[size-1]=0; // 清理无效数据size--;heapifyDown(0);return removedValue; // 占位返回值}// 获取堆顶元素（最大值）public int getMax() {if (size==0) {throw new NoSuchElementException("Heap is empty, no maximum element available.");}return heap[0];}// 获取当前堆的大小public int getSize() {return size;}// 判断堆是否为空public boolean isEmpty() {return size == 0;}// 打印堆内容（可选，用于调试）public void printHeap() {System.out.println(Arrays.toString(Arrays.copyOfRange(heap, 0, size)));}// 向上调整（用于插入操作）private void heapifyUp(int child) {while(child!=0){int parent=(child-1)/2;if (heap[child]>heap[parent]) {swap(child, parent);child=parent;}else {break;}}}// 向下调整（用于删除操作）private void heapifyDown(int parent) {while(true){int leftChild=parent*2+1;int rightChild=parent*2+2;int largest=parent;if (leftChild<size&&heap[leftChild]>heap[largest]){largest=leftChild;}if (rightChild<size&&heap[rightChild]>heap[largest]){largest=rightChild;}if (parent==largest){return;}swap(parent,largest);parent=largest;}}private void expandCapacity(){if (size==heap.length){heap= Arrays.copyOf(heap,size*3/2);}}
}class MyMaxHeapTest {public static void main(String[] args) {// 创建一个最大堆实例MyMaxHeap heap = new MyMaxHeap();// 测试用例 1: 插入元素并打印堆System.out.println("测试用例 1: 插入元素并打印堆");heap.insert(10);heap.insert(20);heap.insert(5);heap.insert(30);heap.insert(15);heap.printHeap(); // 期望输出: [30, 20, 5, 10, 15]// 测试用例 2: 获取堆顶元素System.out.println("\n测试用例 2: 获取堆顶元素");System.out.println("堆顶元素: " + heap.getMax()); // 期望输出: 30// 测试用例 3: 删除堆顶元素并打印堆System.out.println("\n测试用例 3: 删除堆顶元素并打印堆");System.out.println("删除的堆顶元素: " + heap.removeMax()); // 期望输出: 30heap.printHeap(); // 期望输出: [20, 15, 5, 10]// 测试用例 4: 连续删除堆顶元素System.out.println("\n测试用例 4: 连续删除堆顶元素");System.out.println("删除的堆顶元素: " + heap.removeMax()); // 期望输出: 20System.out.println("删除的堆顶元素: " + heap.removeMax()); // 期望输出: 15heap.printHeap(); // 期望输出: [10, 5]// 测试用例 5: 插入更多元素并检查扩容System.out.println("\n测试用例 5: 插入更多元素并检查扩容");heap.insert(50);heap.insert(40);heap.insert(60);heap.insert(70);heap.insert(80);heap.insert(90);heap.insert(100);heap.printHeap(); // 期望输出: [100, 80, 90, 70, 40, 60, 50, 10, 5]// 测试用例 6: 获取堆的大小System.out.println("\n测试用例 6: 获取堆的大小");System.out.println("堆大小: " + heap.getSize()); // 期望输出: 9// 测试用例 7: 判断堆是否为空System.out.println("\n测试用例 7: 判断堆是否为空");System.out.println("堆是否为空: " + heap.isEmpty()); // 期望输出: false// 测试用例 8: 清空堆后操作System.out.println("\n测试用例 8: 清空堆后操作");while (!heap.isEmpty()) {System.out.println("删除的堆顶元素: " + heap.removeMax());}heap.printHeap(); // 期望输出: []// 测试用例 9: 空堆操作异常处理System.out.println("\n测试用例 9: 空堆操作异常处理");try {heap.getMax();} catch (Exception e) {System.out.println("异常捕获: " + e.getMessage()); // 期望输出: Heap is empty. Current size: 0}try {heap.removeMax();} catch (Exception e) {System.out.println("异常捕获: " + e.getMessage()); // 期望输出: Heap is empty. Current size: 0}}
}

3. PriorityQueue

3.1 PriorityQueue的特性

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

图片

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