Java 优先队列详解

简介

在 Java 编程中，优先队列（Priority Queue）是一个非常实用的数据结构。它允许我们按照元素的优先级来处理元素，而不是按照元素插入的顺序。优先队列在许多场景中都有广泛的应用，如任务调度、图算法（如 Dijkstra 算法）等。本文将详细介绍 Java 中优先队列的基础概念、使用方法、常见实践以及最佳实践，帮助读者深入理解并高效使用 Java 优先队列。

基础概念

什么是优先队列

优先队列是一种特殊的队列，它的每个元素都有一个优先级。在出队操作时，优先级最高的元素会被最先移除。在 Java 中，PriorityQueue 类实现了优先队列的功能，它是基于堆（通常是最小堆）数据结构实现的。

堆的概念

堆是一种完全二叉树，分为最大堆和最小堆。在最小堆中，每个节点的值都小于或等于其子节点的值；在最大堆中，每个节点的值都大于或等于其子节点的值。Java 的 PriorityQueue 默认使用最小堆，即队列头部的元素是队列中最小的元素。

使用方法

创建优先队列

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个存储整数的优先队列
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        // 也可以指定初始容量
        PriorityQueue<Integer> priorityQueueWithCapacity = new PriorityQueue<>(10);
    }
}

添加元素

使用 add() 或 offer() 方法向优先队列中添加元素。

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.add(3);
        priorityQueue.offer(1);
        priorityQueue.offer(2);
    }
}

移除元素

使用 poll() 方法移除并返回队列头部的元素，如果队列为空则返回 null；使用 remove() 方法移除并返回队列头部的元素，如果队列为空则抛出 NoSuchElementException 异常。

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(3);
        priorityQueue.offer(1);
        priorityQueue.offer(2);

        Integer firstElement = priorityQueue.poll();
        System.out.println("移除的元素: " + firstElement);
    }
}

查看队列头部元素

使用 peek() 方法查看队列头部的元素，但不移除它，如果队列为空则返回 null；使用 element() 方法查看队列头部的元素，但不移除它，如果队列为空则抛出 NoSuchElementException 异常。

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(3);
        priorityQueue.offer(1);
        priorityQueue.offer(2);

        Integer headElement = priorityQueue.peek();
        System.out.println("队列头部元素: " + headElement);
    }
}

常见实践

任务调度

假设有一组任务，每个任务有一个优先级，我们可以使用优先队列来按照任务的优先级进行调度。

import java.util.PriorityQueue;

class Task implements Comparable<Task> {
    private int priority;
    private String name;

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

    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }

    @Override
    public String toString() {
        return "Task{name='" + name + "', priority=" + priority + "}";
    }
}

public class TaskScheduler {
    public static void main(String[] args) {
        PriorityQueue<Task> taskQueue = new PriorityQueue<>();
        taskQueue.offer(new Task(3, "Task 3"));
        taskQueue.offer(new Task(1, "Task 1"));
        taskQueue.offer(new Task(2, "Task 2"));

        while (!taskQueue.isEmpty()) {
            Task task = taskQueue.poll();
            System.out.println("执行任务: " + task);
        }
    }
}

合并多个有序列表

假设有多个有序列表，我们可以使用优先队列来合并它们。

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class MergeKSortedLists {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode list : lists) {
            if (list != null) {
                pq.offer(list);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            tail.next = node;
            tail = tail.next;
            if (node.next != null) {
                pq.offer(node.next);
            }
        }
        return dummy.next;
    }
}

最佳实践

自定义比较器

如果需要使用最大堆或者对自定义对象进行排序，可以使用自定义比较器。

import java.util.PriorityQueue;

public class CustomComparatorExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap.offer(3);
        maxHeap.offer(1);
        maxHeap.offer(2);

        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }
    }
}

注意线程安全

PriorityQueue 是非线程安全的，如果在多线程环境下使用，需要使用 PriorityBlockingQueue 类。

import java.util.concurrent.PriorityBlockingQueue;

public class ThreadSafePriorityQueueExample {
    public static void main(String[] args) {
        PriorityBlockingQueue<Integer> priorityBlockingQueue = new PriorityBlockingQueue<>();
        priorityBlockingQueue.offer(3);
        priorityBlockingQueue.offer(1);
        priorityBlockingQueue.offer(2);

        Integer element = priorityBlockingQueue.poll();
        System.out.println("移除的元素: " + element);
    }
}

小结

Java 中的优先队列 PriorityQueue 是一个非常实用的数据结构，它基于堆数据结构实现，允许我们按照元素的优先级来处理元素。本文介绍了优先队列的基础概念、使用方法、常见实践以及最佳实践，包括创建队列、添加元素、移除元素、查看元素等操作，以及任务调度、合并多个有序列表等常见应用场景。同时，还介绍了自定义比较器和线程安全的相关内容。希望通过本文的介绍，读者能够深入理解并高效使用 Java 优先队列。

参考资料

《Effective Java》
《算法导论》