用堆实现优先级队列:从基础到实战

举报
bug菌 发表于 2024/10/30 19:59:42 2024/10/30
【摘要】   咦咦咦,各位小可爱,我是你们的好伙伴——bug菌,今天又来给大家普及Java SE相关知识点了,别躲起来啊,听我讲干货还不快点赞,赞多了我就有动力讲得更嗨啦!所以呀,养成先点赞后阅读的好习惯,别被干货淹没了哦~🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,助你一臂之力,带你早日登顶🚀,欢迎大家关注&&收藏!持续更新中,up!up!up!!环境说明:Windows 10 +...

  咦咦咦,各位小可爱,我是你们的好伙伴——bug菌,今天又来给大家普及Java SE相关知识点了,别躲起来啊,听我讲干货还不快点赞,赞多了我就有动力讲得更嗨啦!所以呀,养成先点赞后阅读的好习惯,别被干货淹没了哦~


🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,助你一臂之力,带你早日登顶🚀,欢迎大家关注&&收藏!持续更新中,up!up!up!!

环境说明:Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8

💬 前言

在数据结构和算法的世界里,优先级队列作为一种处理优先级任务的数据结构,极大提升了系统的处理能力。不论是在操作系统的任务调度中,还是在大型服务器的请求处理中,优先级队列都起到至关重要的作用。我们今天要深入探讨的就是如何使用 堆结构 来实现一个优先级队列,用 Java 代码实现,并加以详细分析。让我们一起揭开它的神秘面纱,看看这究竟是如何工作的!

🌟 摘要

本篇文章将通过对优先级队列的基础理论、堆的实现原理和 Java 代码示例来全面剖析如何用堆来构建优先级队列。文章将分为以下几个部分:堆的基础、优先级队列的定义与特点、如何基于堆实现优先级队列、代码实现详解、应用场景展示、优缺点分析、测试与结果分析等。希望读者通过本篇内容,不仅能够掌握优先级队列的实现方式,还能灵活运用到实际开发中。

🧩 简介

优先级队列在许多场景中是一种不可或缺的数据结构。与普通队列不同,优先级队列的插入顺序并不会决定元素的取出顺序,而是由其优先级大小来决定。应用优先级队列的典型场景包括但不限于以下几种:

  • 任务调度:在操作系统中,优先级队列可用于安排紧急任务优先执行。
  • 图的最短路径算法:如 Dijkstra 算法,使用优先级队列保证每次选择的节点是当前路径长度最小的。
  • 事件驱动系统:实时系统中,优先级队列有助于按照优先级顺序处理事件。

我们将在这篇文章中,通过手写 Java 代码从零开始实现一个优先级队列,并分析其各个关键实现细节。相信当你掌握了这部分内容后,对优先级队列的理解会更加深刻!

🗂 概述

堆是一种特殊的完全二叉树,其关键特点在于:父节点的值总是大于或小于其子节点。这使得堆成为实现优先级队列的完美选择。

堆分为两种类型:

  1. 最大堆(Max Heap):父节点的值始终大于等于子节点。
  2. 最小堆(Min Heap):父节点的值始终小于等于子节点。

在优先级队列的实现中,我们通常选择最小堆结构,这样在每次删除时可以直接获得优先级最高的元素,即最小值。堆操作的时间复杂度为 O(log n),它的高效性也是它被广泛使用的原因之一。

接下来,我们将构建一个基于最小堆的优先级队列,并一步步分析其中的实现原理和细节。

🔍 核心源码解读

以下代码实现了一个基本的 最小堆优先级队列,包含添加、取出和查看最小值的功能。每一行代码都包含堆结构的核心逻辑,让我们逐步分析!

import java.util.ArrayList;
import java.util.List;

public class MinHeapPriorityQueue<T extends Comparable<T>> {
    private List<T> heap;

    public MinHeapPriorityQueue() {
        heap = new ArrayList<>();
    }

    public void add(T item) {
        heap.add(item);
        heapifyUp();
    }

    public T poll() {
        if (heap.size() == 0) return null;
        T item = heap.get(0);
        heap.set(0, heap.remove(heap.size() - 1));
        heapifyDown();
        return item;
    }

    public T peek() {
        return heap.isEmpty() ? null : heap.get(0);
    }

    private void heapifyUp() {
        int index = heap.size() - 1;
        while (index > 0 && heap.get(index).compareTo(heap.get(parentIndex(index))) < 0) {
            swap(index, parentIndex(index));
            index = parentIndex(index);
        }
    }

    private void heapifyDown() {
        int index = 0;
        while (leftChildIndex(index) < heap.size()) {
            int smallerChildIndex = leftChildIndex(index);
            if (rightChildIndex(index) < heap.size() &&
                heap.get(rightChildIndex(index)).compareTo(heap.get(leftChildIndex(index))) < 0) {
                smallerChildIndex = rightChildIndex(index);
            }
            if (heap.get(index).compareTo(heap.get(smallerChildIndex)) <= 0) {
                break;
            }
            swap(index, smallerChildIndex);
            index = smallerChildIndex;
        }
    }

    private void swap(int i, int j) {
        T temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    private int parentIndex(int index) {
        return (index - 1) / 2;
    }

    private int leftChildIndex(int index) {
        return 2 * index + 1;
    }

    private int rightChildIndex(int index) {
        return 2 * index + 2;
    }
}

代码解析

  1. 构造器:使用 ArrayList 来储存堆的数据,并动态扩展堆大小。
  2. add 方法:向堆中添加元素并调用 heapifyUp,让新元素上浮到合适位置以保持堆的最小性质。
  3. poll 方法:删除并返回堆顶元素,将堆的最后一个元素移至堆顶后,再调用 heapifyDown 保持堆的最小性质。
  4. peek 方法:返回堆顶元素,不删除。用于查看优先级最高的元素。
  5. 堆调整
    • heapifyUp:在插入时,若新元素小于其父节点,则交换位置以维持最小堆特性。
    • heapifyDown:在移除堆顶元素后,用于调整堆顶位置,保证堆顶元素最小。

具体分析如下:

这段代码实现了一个 最小堆优先级队列,用来存储实现 Comparable 接口的元素,确保每次从队列中取出的都是优先级最高(即数值最小)的元素。让我们逐步解读每个部分的实现和核心逻辑:

1. 类定义与构造器

public class MinHeapPriorityQueue<T extends Comparable<T>> {
    private List<T> heap;

    public MinHeapPriorityQueue() {
        heap = new ArrayList<>();
    }
}
  • heap:使用 ArrayList 来存储堆的元素,模拟一个最小堆结构。
  • 构造方法:初始化 heap 列表。

2. 添加元素 (add 方法)

public void add(T item) {
    heap.add(item);
    heapifyUp();
}
  • add:将新元素 item 添加到堆的末尾,然后调用 heapifyUp 方法,以维持最小堆性质(即父节点值总是小于子节点)。
  • heapifyUp:执行“上浮”操作,将新插入的元素调整到正确位置。

3. 移除优先级最高元素 (poll 方法)

public T poll() {
    if (heap.size() == 0) return null;
    T item = heap.get(0);
    heap.set(0, heap.remove(heap.size() - 1));
    heapifyDown();
    return item;
}
  • poll:移除并返回堆顶元素,即最小的元素(优先级最高)。
    • 如果堆为空,返回 null
    • 取出堆顶元素后,将堆末尾的元素移至堆顶,再调用 heapifyDown 调整堆,使得最小堆性质得以维持。

4. 查看堆顶元素 (peek 方法)

public T peek() {
    return heap.isEmpty() ? null : heap.get(0);
}
  • peek:返回堆顶元素,不进行删除。可以用于查看当前优先级最高的元素。

5. 堆调整方法:heapifyUpheapifyDown

heapifyUp:向上调整元素位置
private void heapifyUp() {
    int index = heap.size() - 1;
    while (index > 0 && heap.get(index).compareTo(heap.get(parentIndex(index))) < 0) {
        swap(index, parentIndex(index));
        index = parentIndex(index);
    }
}
  • 从最后一个元素开始,上浮直到找到正确位置。
  • 该过程不断与父节点比较并交换位置,直到父节点小于或等于当前节点。
heapifyDown:向下调整元素位置
private void heapifyDown() {
    int index = 0;
    while (leftChildIndex(index) < heap.size()) {
        int smallerChildIndex = leftChildIndex(index);
        if (rightChildIndex(index) < heap.size() &&
            heap.get(rightChildIndex(index)).compareTo(heap.get(leftChildIndex(index))) < 0) {
            smallerChildIndex = rightChildIndex(index);
        }
        if (heap.get(index).compareTo(heap.get(smallerChildIndex)) <= 0) {
            break;
        }
        swap(index, smallerChildIndex);
        index = smallerChildIndex;
    }
}
  • 从堆顶开始,找到左右子节点中最小的,与当前节点比较并交换。
  • 该过程重复直到当前节点小于等于其子节点,维持最小堆性质。

6. 辅助方法:swap, parentIndex, leftChildIndex, rightChildIndex

private void swap(int i, int j) {
    T temp = heap.get(i);
    heap.set(i, heap.get(j));
    heap.set(j, temp);
}

private int parentIndex(int index) {
    return (index - 1) / 2;
}

private int leftChildIndex(int index) {
    return 2 * index + 1;
}

private int rightChildIndex(int index) {
    return 2 * index + 2;
}
  • swap:交换堆中两个元素的位置。
  • parentIndex:获取某个节点的父节点索引。
  • leftChildIndexrightChildIndex:获取左、右子节点索引。

小结

MinHeapPriorityQueue 类实现了最小堆优先级队列的基本功能,包括添加、移除和查看优先级最高的元素。它在插入和删除操作上均能保持 O(log n) 的时间复杂度,适用于对元素优先级有严格要求的场景,如任务调度、事件处理等。

堆节点位置关系

在一个完全二叉树的数组表示中:

  • 父节点索引 parent = (i - 1) / 2
  • 左子节点索引 left = 2 * i + 1
  • 右子节点索引 right = 2 * i + 2

通过这些公式,堆结构便能够高效地通过数组完成父子节点之间的跳转操作。

🎉 案例分析:优先级排序演示

我们通过以下代码来测试该优先级队列是否能正确排序。

测试用例

public class Main {
    public static void main(String[] args) {
        MinHeapPriorityQueue<Integer> pq = new MinHeapPriorityQueue<>();
        
        // 插入数据
        pq.add(10);
        pq.add(5);
        pq.add(15);
        pq.add(3);
        pq.add(8);

        // 按优先级顺序输出
        System.out.println("Priority Queue Elements in order:");
        while (pq.peek() != null) {
            System.out.println(pq.poll());  // 期望输出顺序:3, 5, 8, 10, 15
        }
    }
}

预期结果

Priority Queue Elements in order:
3
5
8
10
15

测试代码分析

  1. 插入数据:依次插入 10, 5, 15, 3, 8,优先级越高的元素应当排在越前。
  2. 输出顺序:按优先级顺序依次输出 3, 5, 8, 10, 15,符合最小堆的特性。

详细代码解析如下:这段代码展示了如何使用前面实现的 MinHeapPriorityQueue 类来创建一个最小堆优先级队列,并插入一些整数数据。接下来,我们将详细解读这段代码,包括其结构、功能以及预期的输出。

public class Main {
    public static void main(String[] args) {
        MinHeapPriorityQueue<Integer> pq = new MinHeapPriorityQueue<>();
        
        // 插入数据
        pq.add(10);
        pq.add(5);
        pq.add(15);
        pq.add(3);
        pq.add(8);

        // 按优先级顺序输出
        System.out.println("Priority Queue Elements in order:");
        while (pq.peek() != null) {
            System.out.println(pq.poll());  // 期望输出顺序:3, 5, 8, 10, 15
        }
    }
}

1. 创建优先级队列

MinHeapPriorityQueue<Integer> pq = new MinHeapPriorityQueue<>();
  • 在这里,我们创建了一个 MinHeapPriorityQueue 对象 pq,它专门存储 Integer 类型的数据。这个队列将确保每次弹出元素时,返回的是最小的元素。

2. 插入数据

pq.add(10);
pq.add(5);
pq.add(15);
pq.add(3);
pq.add(8);
  • 我们依次插入了五个整数:10, 5, 15, 3, 8。在插入的过程中,最小堆的结构会根据 heapifyUp 方法进行调整,确保堆的性质得以维持。这样,最小的元素将始终位于堆的顶部。

3. 输出优先级队列中的元素

System.out.println("Priority Queue Elements in order:");
while (pq.peek() != null) {
    System.out.println(pq.poll());  // 期望输出顺序:3, 5, 8, 10, 15
}
  • 我们使用 while 循环,不断调用 peek 方法检查队列是否为空,然后使用 poll 方法弹出并打印出每个元素。
  • 由于我们实现的是一个最小堆,弹出的顺序将是 从小到大 的,因此我们期望的输出顺序是:3, 5, 8, 10, 15

预期输出

运行这段代码后,控制台将打印出:

Priority Queue Elements in order:
3
5
8
10
15

这正是我们预期的顺序。由于 MinHeapPriorityQueue 确保了最小元素在堆顶,每次调用 poll 都会移除并返回当前优先级最高的元素。

小结

这个简单的示例展示了如何利用 MinHeapPriorityQueue 实现一个基本的优先级队列。通过动态插入元素并按照优先级顺序输出,体现了最小堆的高效性和可靠性。在实际应用中,这种数据结构可以用于任务调度、事件管理等场景,以确保更高优先级的任务得到优先处理。

⚙️ 应用场景演示

  1. 任务调度:在操作系统中,优先级队列被用于管理任务,确保高优先级的任务优先处理。
  2. 网络流量控制:在网络系统中,优先级队列可以处理重要的流量或数据包,以确保关键数据包优先传输。
  3. 事件驱动系统:在实时系统中,优先级队列帮助根据优先级来及时响应事件。

⚖️ 优缺点分析

优点

  • 高效的优先级访问:堆结构支持快速查找优先级最高或最低的元素。
  • 高性能的插入和删除:堆在插入和删除操作上的时间复杂度均为 O(log n)
  • 灵活应用:最大堆和最小堆可以按需切换,

适配不同的优先级场景。

缺点

  • 不支持顺序遍历:堆无法按顺序遍历,必须全部弹出。
  • 内存使用较多:对于需要极高性能的场景,堆的操作可能会有小额内存和时间开销。

🔖 总结

通过这篇文章,我们从零实现了基于堆的优先级队列,并结合 Java 代码进行逐步解析,最终实现了一个能有效支持高优先级数据的队列系统。优先级队列在编程实践中至关重要,灵活掌握它可以让你的系统在处理大量任务时具备更高的响应性和调度效率。

✨ 寄语

加油!当你学会了堆和优先级队列的实现后,数据结构的世界将更加丰富有趣,也会帮助你在算法的道路上越走越远!

  …

  好啦,这期的内容就基本接近尾声啦,若你想学习更多,可以参考这篇专栏总结《「滚雪球学Java」教程导航帖》,本专栏致力打造最硬核 Java 零基础系列学习内容,🚀打造全网精品硬核专栏,带你直线超车;欢迎大家订阅持续学习。

🌴附录源码

  如上涉及所有源码均已上传同步在「Gitee」,提供给同学们一对一参考学习,辅助你更迅速的掌握。

☀️建议/推荐你


  无论你是计算机专业的学生,还是对编程有兴趣的小伙伴,都建议直接毫无顾忌的学习此专栏「滚雪球学Java」,bug菌郑重承诺,凡是学习此专栏的同学,均能获取到所需的知识和技能,全网最快速入门Java编程,就像滚雪球一样,越滚越大,指数级提升。

  最后,如果这篇文章对你有所帮助,帮忙给作者来个一键三连,关注、点赞、收藏,您的支持就是我坚持写作最大的动力。

  同时欢迎大家关注公众号:「猿圈奇妙屋」 ,以便学习更多同类型的技术文章,免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板、技术文章Markdown文档等海量资料。

📣Who am I?

我是bug菌,CSDN | 掘金 | InfoQ | 51CTO | 华为云 | 阿里云 | 腾讯云 等社区博客专家,C站博客之星Top30,华为云2023年度十佳博主,掘金多年度人气作者Top40,掘金等各大社区平台签约作者,51CTO年度博主Top12,掘金/InfoQ/51CTO等社区优质创作者;全网粉丝合计 30w+;硬核微信公众号「猿圈奇妙屋」,欢迎你的加入!免费白嫖最新BAT互联网公司面试真题、4000G PDF电子书籍、简历模板等海量资料,你想要的我都有,关键是你不来拿哇。


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。