Java 中实现优先队列

简介

优先队列（Priority Queue）是一种特殊的队列，它的每个元素都有一个优先级，出队时优先级最高的元素会被最先移除。在 Java 中，java.util.PriorityQueue 类提供了优先队列的实现。本文将详细介绍 Java 中优先队列的基础概念、使用方法、常见实践以及最佳实践，帮助读者深入理解并高效使用 Java 优先队列。

基础概念

优先队列定义

优先队列是一种抽象数据类型，它和普通队列不同，普通队列遵循先进先出（FIFO）的原则，而优先队列中元素出队的顺序是根据元素的优先级来决定的，优先级高的元素先出队。

Java 中的优先队列实现

在 Java 中，PriorityQueue 类实现了优先队列。它是基于堆（通常是最小堆）的数据结构实现的，堆是一种完全二叉树，满足堆属性：每个节点的值都小于或等于其子节点的值（最小堆）。

复杂度分析

插入操作（add() 或 offer()）：时间复杂度为 $O(log n)$，其中 $n$ 是队列中元素的数量。
删除操作（remove() 或 poll()）：时间复杂度为 $O(log n)$。
获取队首元素（peek()）：时间复杂度为 $O(1)$。

使用方法

创建优先队列

import java.util.PriorityQueue;

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

插入元素

可以使用 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.add(2);
    }
}

删除元素

使用 remove() 或 poll() 方法删除并返回队首元素。

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.add(2);

        Integer firstElement = priorityQueue.poll();
        System.out.println("First element removed: " + firstElement);
    }
}

获取队首元素

使用 peek() 方法获取队首元素，但不删除它。

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.add(2);

        Integer peekElement = priorityQueue.peek();
        System.out.println("Peek element: " + peekElement);
    }
}

常见实践

自定义优先级

可以通过实现 Comparator 接口来自定义元素的优先级。

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

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

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

public class CustomPriorityQueue {
    public static void main(String[] args) {
        // 自定义比较器，按年龄降序排序
        Comparator<Person> ageComparator = (p1, p2) -> p2.age - p1.age;
        PriorityQueue<Person> priorityQueue = new PriorityQueue<>(ageComparator);

        priorityQueue.add(new Person("Alice", 25));
        priorityQueue.add(new Person("Bob", 30));
        priorityQueue.add(new Person("Charlie", 20));

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

合并多个有序列表

可以使用优先队列来合并多个有序列表。

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

public class MergeSortedLists {
    public static List<Integer> mergeKLists(List<List<Integer>> lists) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        List<Integer> result = new ArrayList<>();

        // 初始化优先队列
        for (int i = 0; i < lists.size(); i++) {
            if (!lists.get(i).isEmpty()) {
                pq.offer(new int[]{lists.get(i).get(0), i, 0});
            }
        }

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int val = current[0];
            int listIndex = current[1];
            int elementIndex = current[2];

            result.add(val);

            if (elementIndex + 1 < lists.get(listIndex).size()) {
                pq.offer(new int[]{lists.get(listIndex).get(elementIndex + 1), listIndex, elementIndex + 1});
            }
        }

        return result;
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = new ArrayList<>();
        lists.add(List.of(1, 4, 5));
        lists.add(List.of(1, 3, 4));
        lists.add(List.of(2, 6));

        List<Integer> mergedList = mergeKLists(lists);
        System.out.println(mergedList);
    }
}

最佳实践

注意线程安全

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

import java.util.concurrent.PriorityBlockingQueue;

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

避免空指针异常

在使用 poll() 或 peek() 方法时，要确保队列不为空，避免空指针异常。

import java.util.PriorityQueue;

public class AvoidNullPointerException {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        if (!priorityQueue.isEmpty()) {
            Integer element = priorityQueue.poll();
            System.out.println(element);
        }
    }
}

小结

本文详细介绍了 Java 中优先队列的基础概念、使用方法、常见实践以及最佳实践。优先队列是一种非常有用的数据结构，在很多场景下都能发挥重要作用，如任务调度、合并有序列表等。在使用时，要注意线程安全和避免空指针异常，同时可以通过自定义比较器来满足不同的优先级需求。

参考资料

《算法导论》
《Effective Java》