首页 > Python资料博客日记

package Demo1;

import java.util.Arrays;

// 堆的自我实现 - 创建堆 + 插入数据 + 删除数据 + 返回堆顶元素 + 判断是否为空
public class MyPriorityQueue {
    public int[] elem; // 存储堆元素的数组
    public int useSize; // 当前堆中元素的个数

    // 初始化堆
    public MyPriorityQueue(int[] array) {
        elem = new int[11]; // 初始化堆的容量
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i]; // 将传入的数组元素放入堆中
            useSize++; // 更新堆中元素的个数
        }
        makeBigHeap(array, useSize); // 创建大根堆
    }

    // 整体创建堆
    public void makeBigHeap(int[] array, int useSize) {
        // 从最后一个非叶子节点开始向上调整
        for (int parent = (useSize - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, useSize); // 对每个非叶子节点进行下沉操作
        }
    }

    // 下沉操作
    private void shiftDown(int root, int useSize) {
        int child = 2 * root + 1; // 左子节点索引
        while (child < useSize) { // 遍历堆
            // 如果右子节点存在且右子节点的值大于左子节点的值，选择右子节点
            if (child + 1 < useSize && elem[child] < elem[child + 1]) {
                child++;
            }
            // 如果当前节点的值小于子节点的值，交换它们
            if (elem[root] < elem[child]) {
                swap(root, child);
                root = child; // 更新根节点为被交换的子节点
                child = 2 * root + 1; // 更新左子节点的索引
            } else {
                break; // 如果根节点的值不小于任何子节点，退出循环
            }
        }
    }

    // 在堆中插入元素
    private boolean isFull() {
        return useSize == elem.length; // 判断堆是否满了
    }

    public void offer(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem, 2 * elem.length); // 扩容
        }
        elem[useSize] = val; // 将新元素放入堆的末尾
        shiftUp(useSize); // 上浮操作调整堆
        useSize++; // 更新堆中元素的个数
    }

    // 上浮操作
    private void shiftUp(int child) {
        int parent = (child - 1) / 2; // 计算父节点的索引
        while (parent >= 0) {
            // 如果当前节点的值大于父节点的值，交换它们
            if (elem[parent] < elem[child]) {
                swap(parent, child);
                child = parent; // 更新子节点为被交换的父节点
                parent = (child - 1) / 2; // 更新父节点的索引
            } else {
                break; // 如果当前节点的值不大于父节点的值，退出循环
            }
        }
    }

    // 删除堆中元素
    public void poll() {
        if (isEmpty()) {
            throw new RuntimeException("堆中元素为空！"); // 如果堆为空，抛出异常
        }
        swap(0, useSize - 1); // 将堆顶元素与最后一个元素交换
        useSize--; // 更新堆中元素的个数
        shiftDown(0, useSize); // 对堆顶元素进行下沉操作
    }

    // 获取堆顶元素
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("堆中元素为空！"); // 如果堆为空，抛出异常
        }
        return elem[0]; // 返回堆顶元素
    }

    // 判断堆是否为空
    private boolean isEmpty() {
        return useSize == 0; // 如果堆中没有元素，返回 true
    }

    // 交换数组中的两个元素
    private void swap(int pos1, int pos2) {
        int temp = elem[pos1];
        elem[pos1] = elem[pos2];
        elem[pos2] = temp;
    }
}

public class Test {
    public static void main(String[] args) {
        // 初始化一个整数数组
        int[] array = {1, 4, 2, 7, 9, 10, 5, 6, 8, 3};
        
        // 创建一个优先级队列实例
        MyPriorityQueue myPriorityQueue = new MyPriorityQueue(array);
        
        // 向优先级队列中插入多个元素
        myPriorityQueue.offer(5);
        myPriorityQueue.offer(3);
        myPriorityQueue.offer(8);
        myPriorityQueue.offer(1);

        // 打印堆顶元素
        System.out.println(myPriorityQueue.peek());

        // 删除堆顶元素
        myPriorityQueue.poll();
        
        // 判断堆是否为空，并打印结果（注意这里原代码并未打印结果，需手动添加打印语句）
        System.out.println("堆是否为空: " + myPriorityQueue.isEmpty());
    }
}

从中我们可以看到我们使用堆这个数据结果来自我实现了从 - 创建堆 - 插入数据 - 删除数据 - 返回堆顶元素 - 判断是否为空等优先队列中的操作。至此我们完成了自我实现Java中的优先级队列（PriorityQueue）。

如果对于堆这种数据结构不了解的读者，可以阅读---------->Java中的Heap（堆）（如果想知道Java中有关堆的知识点，那么只看这一篇就足够了！）-CSDN博客

3.优先级队列中常用API

通过上面的学习，我们已经了解了什么是Java中的优先级队列，并且自我实现了优先级队列，现在让我们看看Java中内置的优先级队列该如何使用吧！

（1）创建优先级队列

PriorityQueue类提供了多种构造方法，允许创建不同配置的优先级队列。

构造器	功能
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则IllegalArgumentException异常
PriorityQueue(Collection<? extends E> c)	用一个集合来创建优先级队列

例子：

import java.util.PriorityQueue;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        // 默认初始容量的优先级队列
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // 指定初始容量的优先级队列
        PriorityQueue<Integer> pqWithCapacity = new PriorityQueue<>(20);
        
        // 使用比较器的优先级队列
        PriorityQueue<Integer> pqWithComparator = new PriorityQueue<>(new CustomComparator());
    }
}

——这样我们就会常见Java中的优先级队列了！

在了解了如何创建一个优先级队列之后，接下来让我们看一下如何去操作这个创建的优先级队列。

（2）插入/删除/获取优先级最高的元素/获取个数/清空/判断是否为空

函数名	功能
boolean offer(E e)	插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度O（logN），注意：空间不够时候会进行扩容
E peek()	获取优先级最高的元素，如果优先级队列为空，返回null
E poll()	移除优先级最高的元素并返回，如果优先级队列为空，返回null
int size()	获取有效元素的个数
void clear()	清空
boolean isEmpty()	检测优先级队列是否为空，空返回true

例子：

import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        // 初始化一个整数数组
        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("优先级队列不为空");
        }
    }
}

——这样我们就大致的了解了如何操作Java中的优先级队列了！！！

4.优先级队列的使用

优先级队列（Priority Queue）是一种特殊的数据结构，用于处理具有优先级的元素。它的主要特点是能够高效地插入元素并以优先级顺序访问和删除元素。以下是优先级队列的一些主要应用场景：

1. 任务调度

场景: 操作系统和调度系统常常需要管理多个任务，每个任务具有不同的优先级。
用法: 优先级队列可以用来实现任务调度系统，其中优先级高的任务会被优先执行。比如，操作系统的进程调度器会使用优先级队列来决定哪个进程应该优先获得 CPU 时间。

2. 事件驱动模拟

场景: 在模拟系统（如网络仿真或离散事件模拟）中，事件会在未来的某个时间点发生。
用法: 优先级队列用于存储和处理这些事件，确保在模拟中按事件的发生时间顺序处理它们。

3. 图算法

场景: 在计算图的最短路径（如 Dijkstra 算法）或最小生成树（如 Prim 算法）时，需要按边的权重或节点的距离进行操作。
用法: 使用优先级队列可以有效地管理和访问图中的边或节点，以支持这些算法的高效执行。

4. 数据流处理

场景: 数据流中的数据可能具有不同的重要性或优先级。
用法: 在处理实时数据流时，优先级队列可以用来根据数据的优先级顺序处理数据。

这样我们就大致的了解了Java中的优先级队列在日常中的使用地方了！

以上就是本篇文章的全部内容了~~~

标签：

上一篇：【Python基础】Python中处理JSON文件的全面指南
下一篇：100个python的基本语法知识【下】

点击排行

本站推荐

标签云

Python高手进阶指南

首页 > Python资料博客日记

Java中的优先级队列（PriorityQueue）（如果想知道Java中有关优先级队列的知识点，那么只看这一篇就足够了！）

1.优先队列的初识

（1）优先级队列的定义

（2）PriorityQueue的特性

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

3.优先级队列中常用API

（1）创建优先级队列

（2）插入/删除/获取优先级最高的元素/获取个数/清空/判断是否为空

4.优先级队列的使用

1. 任务调度

2. 事件驱动模拟

3. 图算法

4. 数据流处理

相关文章

最新发布

点击排行

本站推荐

标签云

首页 > Python资料 博客日记

Java中的优先级队列（PriorityQueue）（如果想知道Java中有关优先级队列的知识点，那么只看这一篇就足够了！）

1.优先队列的初识

（1）优先级队列的定义

（2）PriorityQueue的特性

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

3.优先级队列中常用API

（1）创建优先级队列

（2）插入/删除/获取优先级最高的元素/获取个数/清空/判断是否为空

4.优先级队列的使用

1. 任务调度

2. 事件驱动模拟

3. 图算法

4. 数据流处理

相关文章

最新发布

点击排行

本站推荐

标签云

首页 > Python资料博客日记