Java 中 PriorityQueue 的底层数据结构及相关分析

Java 中 PriorityQueue 的底层数据结构及相关分析

1. PriorityQueue 的底层数据结构

在 Java 中，PriorityQueue 的底层数据结构是基于堆（Heap）实现的二叉堆（Binary Heap），默认使用最小堆（Min Heap），即堆顶元素是队列中的最小元素。

PriorityQueue 采用数组（Object[]）**来存储数据，并使用**二叉堆结构来维护优先级关系。

2. PriorityQueue 的实现原理

2.1 插入（offer/add）

• 新元素插入到堆的末尾（数组的最后一个位置）。
• 通过**上浮（siftUp）**操作，确保堆的有序性。
• 上浮操作通过比较当前节点与其父节点的大小，若当前节点比父节点小，则交换它们，直到满足最小堆的性质。

2.2 删除（poll/remove）

• 删除堆顶元素（最小元素）。
• 用堆的最后一个元素填补堆顶位置。
• 通过**下沉（siftDown）**操作，确保堆的有序性。
• 下沉操作通过比较当前节点与其子节点的大小，若当前节点大于子节点，则交换它们，直到满足最小堆的性质。

2.3 获取堆顶元素（peek）

• 直接返回数组的第一个元素（堆顶）。
• 时间复杂度 O(1)。

2.4 复杂度分析

• 插入（offer/add）：O(log n)
• 删除（poll/remove）：O(log n)
• 访问堆顶元素（peek）：O(1)

3. PriorityQueue 的应用场景

1. 任务调度（按优先级处理任务）
2. Dijkstra 最短路径算法
3. Top K 问题（获取前 K 个最大/最小元素）
4. 流式数据处理（如实时求中位数）
5. 操作系统进程调度（按照优先级处理不同任务）
6. 数据合并（如合并多个有序数组）

4. PriorityQueue 的优缺点

4.1 优点

• 自动维护有序性，取最小/最大元素效率高。
• 插入、删除操作高效，时间复杂度 O(log n)。
• 基于堆的高效实现，适用于大量数据的优先级处理。

4.2 缺点

• 不支持随机访问，不能像 ArrayList 一样通过索引直接访问。
• 只保证堆顶元素是最小/最大，无法保证整体有序。
• 非线程安全，如需多线程使用，可考虑 PriorityBlockingQueue。

5. 替代方案

6. PriorityQueue 使用示例

6.1 基本用法

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建最小堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        pq.offer(7);
        pq.offer(2);

        // 依次取出最小元素
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

输出：

1
2
3
5
7

6.2 自定义排序（最大堆）

import java.util.Collections;
import java.util.PriorityQueue;

public class MaxHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(5);
        maxHeap.offer(1);
        maxHeap.offer(3);
        maxHeap.offer(7);
        maxHeap.offer(2);
        
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }
    }
}

输出：

7
5
3
2
1

6.3 自定义对象排序

import java.util.PriorityQueue;
import java.util.Comparator;

class Task {
    String name;
    int priority;
    
    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public String toString() {
        return name + " (Priority: " + priority + ")";
    }
}

public class TaskScheduler {
    public static void main(String[] args) {
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(t -> t.priority));
        taskQueue.offer(new Task("Task A", 3));
        taskQueue.offer(new Task("Task B", 1));
        taskQueue.offer(new Task("Task C", 2));
        
        while (!taskQueue.isEmpty()) {
            System.out.println(taskQueue.poll());
        }
    }
}

输出：

Task B (Priority: 1)
Task C (Priority: 2)
Task A (Priority: 3)

7. 总结

1. 底层结构：基于二叉堆，使用数组存储。
2. 操作复杂度：插入/删除 O(log n)，访问 O(1)。
3. 应用场景：任务调度、最短路径、Top K 等。
4. 优缺点：自动排序但不支持随机访问，非线程安全。
5. 替代方案：线程安全用 PriorityBlockingQueue，基于红黑树用 TreeSet。

PriorityQueue 是 Java 中处理优先级任务的高效工具，在需要动态维护最小或最大元素的场景下非常有用。