Java高手的30k之路｜面试宝典｜精通PriorityQueue优先队列

本文主要是介绍Java高手的30k之路｜面试宝典｜精通PriorityQueue优先队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PriorityQueue

PriorityQueue 是 Java 集合框架中的一个队列实现，基于优先级堆（优先队列），它能够保证每次出队的元素都是当前队列中优先级最高的元素（对于最小堆而言，优先级最高即为最小值）。其内部实现通常为最小堆或最大堆。

特点

• 基于堆的实现：PriorityQueue 底层基于堆（通常是最小堆）实现，因此能够在 O(log n) 时间复杂度内完成插入和删除操作。
  • ⚠️ 最小堆，即值最小的元素在最上面，其余所有值都比它大，对应到数组中，索引为0的第一个元素就是值最小的元素，此处值小视为优先级大，举个例子，1表示优先级最高，2表示次优先级
• 自然顺序或自定义顺序：可以使用元素的自然顺序（通过实现 Comparable 接口）或提供一个 Comparator 来自定义顺序。
  • ⚠️ 可以存在相同优先级的元素，但是顺序不能保证
• 无序性：PriorityQueue 并不保证元素的顺序，但保证优先级最高的元素总是位于队首。
• 不允许 null 元素：PriorityQueue 不允许插入 null 元素，以避免在比较时出现 NullPointerException。

使用场景

• 任务调度：适用于调度系统中需要按优先级处理任务的场景。
• 路径查找算法：如 Dijkstra 算法，A* 搜索算法等，需要优先处理优先级高的节点。
• 实时处理系统：需要根据优先级动态处理事件或数据的场景。

任务调度中的优先级处理任务示例：医院急诊室

假设我们有一个医院的急诊室（ER），在这个急诊室里，病人的治疗优先级根据他们的病情严重程度来决定。医院的管理系统需要根据优先级来处理这些病人的治疗顺序。这个场景非常适合使用一个优先级队列（PriorityQueue）来调度任务。

场景描述

1. 病人分类：病人进入急诊室时，会由护士进行初步检查和分类。根据病情严重程度，病人被分为不同的优先级：

   • 1级（最高优先级）：危及生命的病情，如心脏病发作、严重外伤等。
   • 2级（较高优先级）：严重但不立即危及生命的病情，如严重骨折、高烧等。
   • 3级（中等优先级）：需要尽快处理但不属于紧急情况的病情，如轻微骨折、中度发烧等。
   • 4级（低优先级）：可以等待的病情，如轻微感冒、轻度擦伤等。

2. 病人治疗：医生会根据病人的优先级顺序进行治疗。优先级高的病人会优先被医生处理。

代码示例

我们可以使用Java中的PriorityQueue来模拟这个过程。

import java.util.PriorityQueue;class Patient implements Comparable<Patient> {private String name;private int severity;public Patient(String name, int severity) {this.name = name;this.severity = severity;}public String getName() {return name;}public int getSeverity() {return severity;}@Overridepublic int compareTo(Patient other) {// 优先级队列按病情严重程度排序，严重程度越高（数值越低），优先级越高return Integer.compare(this.severity, other.severity);}@Overridepublic String toString() {return "Patient{name='" + name + "', severity=" + severity + '}';}
}public class EmergencyRoom {public static void main(String[] args) {PriorityQueue<Patient> emergencyRoomQueue = new PriorityQueue<>();// 添加病人到优先级队列中emergencyRoomQueue.add(new Patient("John Doe", 2));emergencyRoomQueue.add(new Patient("Jane Smith", 1));emergencyRoomQueue.add(new Patient("Jim Brown", 3));emergencyRoomQueue.add(new Patient("Jake White", 4));// 处理病人while (!emergencyRoomQueue.isEmpty()) {Patient patient = emergencyRoomQueue.poll();System.out.println("Treating patient: " + patient);}}
}

解释

• 病人类（Patient）：病人有名字和病情严重程度。实现Comparable接口使得病人可以按严重程度排序。
• 优先级队列（PriorityQueue）：用来存储和排序病人。病情越严重（数值越小），优先级越高。
• 处理病人：从优先级队列中取出病人进行治疗，病情最严重的病人会首先被处理。

Dijkstra 算法与 PriorityQueue 结合的路径查找示例

Dijkstra算法是一种用于寻找图中节点之间最短路径的算法。它广泛应用于网络路由、地图导航等领域。该算法使用优先级队列来高效地选择当前最短路径的节点。

示例场景

假设我们有一个带权重的无向图，图中节点代表城市，边的权重代表城市之间的距离。我们需要找到从起点城市到其他所有城市的最短路径。

      10A ------- B| \       |1|  \9    |5|    \    |C------- D7 

• 边 (A, B) 的权重为 10
• 边 (A, C) 的权重为 1
• 边 (A, D) 的权重为 9
• 边 (B, D) 的权重为 5
• 边 (C, D) 的权重为 7

代码实现

import java.util.*;class Node implements Comparable<Node> {public final String name;public int distance = Integer.MAX_VALUE;public List<Edge> edges = new ArrayList<>();public Node(String name) {this.name = name;}@Overridepublic int compareTo(Node other) {return Integer.compare(this.distance, other.distance);}
}class Edge {public final Node target;public final int weight;public Edge(Node target, int weight) {this.target = target;this.weight = weight;}
}public class DijkstraExample {public static void main(String[] args) {// 创建图的节点Node nodeA = new Node("A");Node nodeB = new Node("B");Node nodeC = new Node("C");Node nodeD = new Node("D");// 创建图的边nodeA.edges.add(new Edge(nodeB, 10));nodeA.edges.add(new Edge(nodeC, 1));nodeA.edges.add(new Edge(nodeD, 9));nodeB.edges.add(new Edge(nodeD, 5));nodeC.edges.add(new Edge(nodeD, 7));// 创建节点集合List<Node> nodes = Arrays.asList(nodeA, nodeB, nodeC, nodeD);// 执行 Dijkstra 算法dijkstra(nodeA);// 输出从起点到所有节点的最短路径距离for (Node node : nodes) {System.out.println("Distance from A to " + node.name + " is " + node.distance);}}public static void dijkstra(Node source) {source.distance = 0;PriorityQueue<Node> queue = new PriorityQueue<>();queue.add(source);while (!queue.isEmpty()) {Node current = queue.poll();for (Edge edge : current.edges) {Node target = edge.target;int distanceThroughCurrent = current.distance + edge.weight;if (distanceThroughCurrent < target.distance) {queue.remove(target);target.distance = distanceThroughCurrent;queue.add(target);}}}}
}

详细步骤说明

1. 初始化节点：为每个节点创建一个对象，初始化其名称、距离和邻接边列表。
2. 创建边：为每个节点创建与其他节点相连的边，并设置边的权重。
3. Dijkstra 算法初始化：
   • 将起始节点的距离设为 0（表示从起始节点到自身的距离为 0）。
   • 将所有节点添加到优先级队列中。
4. 处理队列中的节点：
   • 从优先级队列中取出距离最短的节点（初始时为起始节点）。
   • 对于该节点的每个邻接节点，计算从起始节点经过当前节点到达该邻接节点的距离。
   • 如果新计算的距离比当前记录的距离短，则更新该邻接节点的距离，并将其重新添加到优先级队列中。
5. 重复步骤 4，直到优先级队列为空。

解释

• 优先级队列：PriorityQueue 在这里用于高效地选择当前距离最短的节点进行处理。每次从队列中取出的节点都是当前最短路径的节点。
• 节点距离更新：通过检查和更新邻接节点的距离，确保每个节点记录的距离始终是从起始节点到达该节点的最短距离。

示例代码

import java.util.PriorityQueue;public class PriorityQueueExample {public static void main(String[] args) {// 创建一个 PriorityQueuePriorityQueue<Integer> pq = new PriorityQueue<>();// 添加元素pq.offer(10);pq.offer(20);pq.offer(15);// 获取并移除队首元素System.out.println("Polling: " + pq.poll());  // 输出 10// 获取队首元素但不移除System.out.println("Peek: " + pq.peek());  // 输出 15// 遍历元素pq.forEach(element -> System.out.println("Element: " + element));}
}

内部实现

PriorityQueue 底层使用一个数组（Object[] queue）来存储元素。该数组是动态扩展的，当容量不足时会自动扩容。

• 插入元素：插入元素时，会将新元素添加到堆的末尾，然后通过上浮操作（heapify-up）维持堆的性质。
• 删除元素：删除元素时，会将堆顶元素移除，并将堆末尾的元素移动到堆顶，然后通过下沉操作（heapify-down）维持堆的性质。

核心操作

1. 插入元素

   插入元素时，PriorityQueue 会将新元素添加到数组的末尾，然后通过上浮操作（sift up）将其放置到正确的位置，以维持堆的性质。

   private void siftUpComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>) x;while (k > 0) {int parent = (k - 1) >>> 1;Object e = queue[parent];if (key.compareTo((E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = key;
   }
   

2. 删除元素

   删除堆顶元素时（即优先级最高的元素），PriorityQueue 会将最后一个元素移动到堆顶，然后通过下沉操作（sift down）将其放置到正确的位置，以维持堆的性质。

   private void siftDownComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>)x;int half = size >>> 1; // loop while a non-leafwhile (k < half) {int child = (k << 1) + 1; // assume left child is leastObject c = queue[child];int right = child + 1;if (right < size &&((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)c = queue[child = right];if (key.compareTo((E) c) <= 0)break;queue[k] = c;k = child;}queue[k] = key;
   }
   

3. 扩容

   当数组容量不足时，PriorityQueue 会通过复制现有数组并将其大小增加一倍来进行扩容。

   private void grow(int minCapacity) {int oldCapacity = queue.length;// Double size if small; else grow by 50%int newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity + 2) :(oldCapacity >> 1));// overflow-conscious codeif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);
   }
   

注意事项

• 不保证元素顺序：PriorityQueue 仅保证优先级最高的元素在队首，并不保证其他元素按优先级有序。
• 线程安全：PriorityQueue 不是线程安全的，在并发环境中使用时需要额外的同步措施，如使用 PriorityBlockingQueue。
• 比较器一致性：提供的比较器应当与元素的 equals 方法一致，否则可能导致不可预知的行为。

最佳实践

• 合适的初始容量：在创建 PriorityQueue 时，可以指定初始容量以避免频繁扩容。
• 避免 null 元素：确保不插入 null 元素，以避免在堆操作时出现 NullPointerException。
• 合理的 Comparator：如果使用自定义顺序，提供一个合理且性能优良的 Comparator 实现。

堆

堆（Heap）

堆是一种特殊的树形数据结构，它满足以下特性：

1. 完全二叉树：堆总是完全二叉树，即除了最后一层外，每一层都是满的，并且最后一层的节点尽可能靠左。
2. 堆性质：每个节点的值都大于或小于其子节点的值，这决定了堆的类型。

堆通常有两种类型：

• 最大堆（Max Heap）：每个节点的值都大于或等于其子节点的值，堆顶元素是最大值。
• 最小堆（Min Heap）：每个节点的值都小于或等于其子节点的值，堆顶元素是最小值。

最大堆示例

        10/  \9    8/ \  / \7  6 5   4/ \3   2

最小堆示例

        1/ \3   2/ \ / \7  6 5  4/ \9  8

最小堆（Min Heap）

最小堆是一种堆数据结构，其中每个节点的值都小于或等于其子节点的值。它具有以下特性：

1. 根节点最小：堆顶（根节点）的元素是整个堆中最小的。
2. 部分有序：堆的任意子树都是一个最小堆。

操作

• 插入：将新元素添加到堆的末尾，然后通过“上浮”操作（调整位置，使新元素上升到适当位置）维持堆性质。
• 删除最小元素：将堆顶元素（最小元素）移除，并将堆的最后一个元素移到堆顶，然后通过“下沉”操作（调整位置，使该元素下沉到适当位置）维持堆性质。
• 堆化：对一个无序数组进行调整，构建一个最小堆。

插入操作示例

将元素 0 插入到以下最小堆：

        1/ \3   2/ \ / \7  6 5  4/ \9  8

结果为：

        0/ \3   1/ \ / \7  6 5  2/ \9  8

删除操作示例

从以下最小堆中删除根节点：

        1/ \3   2/ \ / \7  6 5  4/ \9  8

结果为：

        2/ \3   4/ \ / \7  6 5  8/9

堆的应用

堆广泛应用于以下场景：

• 优先队列：使用最小堆或最大堆实现优先队列，确保每次出队的是优先级最高或最低的元素。
• 排序算法：堆排序利用堆的性质对数组进行排序，时间复杂度为 O(n log n)。
• 图算法：在 Dijkstra 最短路径算法和 Prim 最小生成树算法中使用最小堆提高效率。
• 内存管理：操作系统的内存管理系统使用堆数据结构分配和释放内存。

这篇关于Java高手的30k之路｜面试宝典｜精通PriorityQueue优先队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---