本文共 3050 字，大约阅读时间需要 10 分钟。

优先队列：从数据结构到实现

前言

事情要从一个故事讲起。在这里，我们遇到了一个可爱的小狗狗，它对数据结构的知识表现得非常有趣。为了帮助它更好地理解优先队列，我们决定从基础的数据结构入手。

在这里，我们将介绍优先队列的设计与实现，结合手写代码的过程，帮助你深入理解这一数据结构的核心原理。

堆

堆是一种特殊的数据结构，可以被看作是一棵完全二叉树。堆的特点是：

堆分为两种类型：

• 大根堆：父节点大于子节点。
• 小根堆：父节点小于子节点。

堆在实际应用中通常使用数组来存储，尽管完全二叉树的实现可能涉及链式结构，但在大多数情况下，数组实现更为常见，因为它具有较高的空间利用率。

优先队列

优先队列是一种特殊的队列，它的核心特性是支持根据优先级快速获取或删除元素。与普通队列不同，优先队列遵循先取最大或最小的规则，默认情况下通常是取最小的。

优先队列的基本操作包括：

插入流程

删除流程

代码实现

为了更深入理解优先队列，我们尝试手写一个简易型的优先队列。以下是主要操作的代码实现：

import java.util.Arrays;public class PriQueue {    private int size;    private int capacity;    private int[] value;    public PriQueue() {        this.capacity = 10;        this.value = new int[capacity];        this.size = 0;    }    public PriQueue(int capacity) {        this.capacity = capacity;        this.value = new int[capacity];        this.size = 0;    }    public void add(int number) {        if (size == capacity) {            capacity *= 1.5;            value = Arrays.copyOf(value, capacity);        }        value[size++] = number;        int index = size - 1;        while (index >= 1) {            if (value[index] < value[index / 2]) {                swap(index, index / 2, value);            } else {                break;            }            index /= 2;        }    }    public int poll() {        if (size == 0) {            return -1; // 表示队列为空        }        int index = 0;        int temp = value[size];        value[size] = value[0];        size--;        index = size;        while (index > 0) {            int left = index * 2 + 1;            int right = index * 2 + 2;            if (left >= size) {                break;            }            if (value[left] < value[index] || value[right < size && value[right] < value[index])) {                if (left < size && value[left] < value[index]) {                    index = left;                } else if (right < size && value[right] < value[index]) {                    index = right;                } else {                    break;                }            } else {                break;            }            index = index / 2;        }        value[index] = temp;        return value[0];    }    public int peek() {        if (size == 0) {            return -1; // 表示队列为空        }        return value[0];    }}

测试代码

public class Main {    public static void main(String[] args) {        PriQueue pq = new PriQueue();        pq.add(3);        pq.add(2);        pq.add(5);        pq.add(1);        System.out.println("队列：" + Arrays.toString(pq.value));        System.out.println("peek：" + pq.peek());        System.out.println("poll：" + pq.poll());        System.out.println("队列：" + Arrays.toString(pq.value));    }}

结语

优先队列的设计与实现是一个非常有趣的过程。通过以上内容，你已经掌握了优先队列的核心原理和实现方法。希望这篇文章能为你的学习之路提供一些帮助。

如果你喜欢这篇文章，请记得点赞或分享给更多的朋友。如果你想了解更多技术内容，可以关注我的公众号：bigsai，回复“bigsai”获取更多干货和资源。

转载地址：http://pvvkz.baihongyu.com/