PriorityQueue

优先队列（基于最小堆实现），数值越小优先级越高。

函数签名

function createPriorityQueue<T>(): PriorityQueue<T>

interface PriorityQueue<T> {
  enqueue(item: T, priority: number): void
  dequeue(): T | undefined
  peek(): T | undefined
  size(): number
  isEmpty(): boolean
  clear(): void
  toArray(): PriorityQueueItem<T>[]
}

interface PriorityQueueItem<T> {
  value: T
  priority: number
}

API 说明

enqueue(item: T, priority: number): void

将元素添加到优先队列中。

参数：

• item: 要添加的元素
• priority: 优先级（数值越小优先级越高）

时间复杂度：O(log n)

dequeue(): T | undefined

移除并返回优先级最高的元素。

返回值：

• 优先级最高的元素，如果队列为空则返回 undefined

时间复杂度：O(log n)

peek(): T | undefined

查看优先级最高的元素，但不移除。

返回值：

• 优先级最高的元素，如果队列为空则返回 undefined

时间复杂度：O(1)

size(): number

获取队列中元素的数量。

返回值：

• 队列中元素的数量

时间复杂度：O(1)

isEmpty(): boolean

检查队列是否为空。

返回值：

• 如果队列为空则返回 true，否则返回 false

时间复杂度：O(1)

clear(): void

清空队列中的所有元素。

时间复杂度：O(1)

toArray(): PriorityQueueItem<T>[]

返回队列中所有元素的数组副本（按优先级排序）。

返回值：

• 包含所有元素及其优先级的数组

时间复杂度：O(n log n)

使用示例

import { createPriorityQueue } from '@shared/functions/data-structures/PriorityQueue'

// 创建优先队列
const pq = createPriorityQueue<string>()

// 添加任务（优先级越小越高）
pq.enqueue('低优先级任务', 10)
pq.enqueue('紧急任务', 1)
pq.enqueue('中优先级任务', 5)
pq.enqueue('高优先级任务', 2)

// 查看最高优先级任务
console.log(pq.peek())  // '紧急任务'

// 按优先级依次出队
console.log(pq.dequeue())  // '紧急任务' (优先级 1)
console.log(pq.dequeue())  // '高优先级任务' (优先级 2)
console.log(pq.dequeue())  // '中优先级任务' (优先级 5)
console.log(pq.dequeue())  // '低优先级任务' (优先级 10)

// 队列为空
console.log(pq.isEmpty())  // true

工作原理

优先队列基于最小堆数据结构实现：

1. 堆结构：完全二叉树，父节点优先级总是小于或等于子节点
2. 上浮操作（Heapify Up）：新元素添加到堆底，然后与父节点比较并交换，直到满足堆性质
3. 下沉操作（Heapify Down）：移除堆顶后，将最后一个元素移到堆顶，然后与子节点比较并交换，直到满足堆性质

堆的数组表示：

• 父节点索引：Math.floor((i - 1) / 2)
• 左子节点索引：2 * i + 1
• 右子节点索引：2 * i + 2

应用场景

1. 任务调度：操作系统中的进程调度
2. Dijkstra 算法：求最短路径
3. Huffman 编码：数据压缩
4. 事件驱动模拟：按时间顺序处理事件
5. Top K 问题：找出前 K 个最大/最小元素
6. 合并 K 个有序链表：LeetCode 经典问题

经典算法

Dijkstra 最短路径算法

interface Edge {
  to: number
  weight: number
}

function dijkstra(graph: Edge[][], start: number): number[] {
  const n = graph.length
  const dist = Array(n).fill(Infinity)
  dist[start] = 0
  
  const pq = createPriorityQueue<number>()
  pq.enqueue(start, 0)
  
  while (!pq.isEmpty()) {
    const u = pq.dequeue()!
    
    for (const edge of graph[u]) {
      const v = edge.to
      const newDist = dist[u] + edge.weight
      
      if (newDist < dist[v]) {
        dist[v] = newDist
        pq.enqueue(v, newDist)
      }
    }
  }
  
  return dist
}

Top K 频率最高的元素

function topKFrequent(nums: number[], k: number): number[] {
  // 统计频率
  const freq = new Map<number, number>()
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1)
  }
  
  // 使用优先队列（大优先级）
  const pq = createPriorityQueue<number>()
  for (const [num, count] of freq) {
    pq.enqueue(num, -count)  // 负数使大的频率有高优先级
  }
  
  // 取出前 K 个
  const result: number[] = []
  for (let i = 0; i < k && !pq.isEmpty(); i++) {
    result.push(pq.dequeue()!)
  }
  
  return result
}

console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2))  // [1, 2]

性能特点

操作	时间复杂度
入队	O(log n)
出队	O(log n)
查看	O(1)
空间	O(n)

优先队列在需要频繁获取最大/最小值的场景中非常高效，比普通排序数组（O(n log n)）或每次线性查找（O(n)）都要快。