优先队列在LeetCode中的应用与解析

优先队列（Priority Queue）是一种特殊的队列数据结构，其中的元素按照优先级进行排序。优先级最高的元素总是位于队列的头部，优先出队。在LeetCode中，优先队列是一个非常重要的工具，广泛应用于各种算法问题中。本文将详细介绍优先队列在LeetCode中的应用，并列举一些经典的题目。

优先队列的基本概念

优先队列可以看作是一个堆（Heap），通常使用二叉堆实现。堆是一种特殊的完全二叉树，满足堆性质：父节点的键值总是大于或等于（小于或等于）其子节点的键值。在LeetCode中，优先队列常用于解决以下几类问题：

排序问题：通过堆排序实现快速排序。
Top K问题：找出数组中前K个最大的或最小的元素。
调度问题：如任务调度、作业调度等。
图算法：如Dijkstra最短路径算法、Prim最小生成树算法。

LeetCode中的经典题目

1. 合并K个排序链表（Merge K Sorted Lists）

题目描述：给定一个由K个排序链表组成的数组，将所有链表合并为一个排序的链表。

解决方案：使用优先队列，每次从队列中取出最小的节点，加入到结果链表中，并将该节点的下一个节点加入优先队列。

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    dummy = ListNode(0)
    curr = dummy
    heap = []
    for i, l in enumerate(lists):
        if l:
            heapq.heappush(heap, (l.val, i, l))

    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

2. 找出第K大的元素（Kth Largest Element in an Array）

题目描述：在未排序的数组中找到第K大的元素。

解决方案：使用优先队列维护一个大小为K的最小堆，堆顶元素即为第K大的元素。

import heapq

def findKthLargest(nums, k):
    heap = []
    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        elif num > heap[0]:
            heapq.heapreplace(heap, num)
    return heap[0]

3. 任务调度器（Task Scheduler）

题目描述：给定一组任务和冷却时间n，计算完成所有任务的最短时间。

解决方案：使用优先队列来模拟任务的执行过程，确保在冷却时间内不重复执行同一个任务。

import heapq
from collections import Counter

def leastInterval(tasks, n):
    task_counts = Counter(tasks)
    heap = [-count for count in task_counts.values()]
    heapq.heapify(heap)
    time = 0
    while heap:
        temp = []
        for _ in range(n + 1):
            if heap:
                count = heapq.heappop(heap)
                if count + 1 < 0:
                    temp.append(count + 1)
            time += 1
            if not heap and not temp:
                break
        for count in temp:
            heapq.heappush(heap, count)
    return time

总结

优先队列在LeetCode中的应用非常广泛，它不仅能提高算法的效率，还能简化问题的解决思路。通过上述几个例子，我们可以看到优先队列在排序、查找、调度等问题中的强大作用。掌握优先队列的使用，不仅能在LeetCode中取得更好的成绩，还能在实际编程中解决复杂的调度和优化问题。希望本文能帮助大家更好地理解和应用优先队列，提升自己的算法能力。