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

原创

bug菌

发布于 2024-11-29 08:53:40

5030

好事发生

这里推荐一篇实用的文章：《Java中合并多个对象的List数据详解》，作者：【喵手】。

这篇文章作者主要讲解如何在 Java 中高效合并多个对象的 List 数据。首先，我们会简要介绍 List 在 Java 中的使用，然后解析不同的 List 合并方法，并展示相应的代码实现。随后，通过具体案例展示合并操作的实际应用场景，最后对各方法的优缺点进行分析，并提供核心方法和测试用例帮助读者理解 ...借此好文安利给大家。

OK，那本期正文即将拉开帷幕。

🏆本文收录于「滚雪球学Java」专栏中，这个专栏专为有志于提升Java技能的你打造，覆盖Java编程的方方面面，助你从零基础到掌握Java开发的精髓。赶紧关注，收藏，学习吧！

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

💬 前言

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

🌟 摘要

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

🧩 简介

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

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

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

🗂 概述

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

堆分为两种类型：

最大堆（Max Heap）：父节点的值始终大于等于子节点。
最小堆（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;
    }
}

代码解析

构造器：使用 ArrayList 来储存堆的数据，并动态扩展堆大小。
add 方法：向堆中添加元素并调用 heapifyUp，让新元素上浮到合适位置以保持堆的最小性质。
poll 方法：删除并返回堆顶元素，将堆的最后一个元素移至堆顶后，再调用 heapifyDown 保持堆的最小性质。
peek 方法：返回堆顶元素，不删除。用于查看优先级最高的元素。
堆调整：
- 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. 堆调整方法：`heapifyUp` 和 `heapifyDown`

`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：获取某个节点的父节点索引。
leftChildIndex 和 rightChildIndex：获取左、右子节点索引。

小结

该 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

测试代码分析

插入数据：依次插入 10, 5, 15, 3, 8，优先级越高的元素应当排在越前。
输出顺序：按优先级顺序依次输出 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 实现一个基本的优先级队列。通过动态插入元素并按照优先级顺序输出，体现了最小堆的高效性和可靠性。在实际应用中，这种数据结构可以用于任务调度、事件管理等场景，以确保更高优先级的任务得到优先处理。

⚙️ 应用场景演示

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

⚖️ 优缺点分析

优点

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

适配不同的优先级场景。

缺点

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

🔖 总结

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

✨ 寄语

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

☀️建议/推荐你

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

码字不易，如果这篇文章对你有所帮助，帮忙给bug菌来个一键三连(关注、点赞、收藏) ，您的支持就是我坚持写作分享知识点传播技术的最大动力。同时也推荐大家关注我的硬核公众号:「猿圈奇妙屋」；以第一手学习bug菌的首发干货，不仅能学习更多技术硬货，还可白嫖最新BAT大厂面试真题、4000G Pdf技术书籍、万份简历/PPT模板、技术文章Markdown文档等海量资料，你想要的我都有！

📣关于我

我是bug菌，CSDN | 掘金 | 腾讯云 | 华为云 | 阿里云 | 51CTO | InfoQ 等社区博客专家，历届博客之星Top30，掘金年度人气作者Top40，51CTO年度博主Top12，掘金等平台签约作者，华为云 | 阿里云| 腾讯云等社区优质创作者，全网粉丝合计30w+ ；硬核微信公众号「猿圈奇妙屋」，欢迎你的加入！免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板等海量资料。

--End

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S10

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S10

登录后参与评论

0 条评论

热度