优先队列详解

FUQFY • 2025-02-01 13:34 • 编程

优先队列（Priority Queue）是一种抽象数据类型，它和普通队列（Queue）的区别在于，每个元素都有一个优先级，并且按照优先级的高低来决定元素的出队顺序。优先队列可以使用数组、链表、堆等结构来实现。

一、基本介绍

优先队列的基本操作包括：

Insert：将一个元素加入队列
Remove：删除队列中优先级最高的元素
Peek：查看队列中优先级最高的元素

我们可以使用一个数组来实现优先队列，每个元素存储元素的值和优先级，然后根据优先级对数组进行排序。但是这种实现方法的时间复杂度为O(nlogn)，不够高效。更高效的实现方法是使用堆结构来实现。

二、堆结构

堆是一种完全二叉树，满足以下两个条件：

父节点的值总是大于（或小于）它的子节点的值
除了最下面一层，其他层的节点都是满的

堆分为大根堆（Max Heap）和小根堆（Min Heap），在大根堆中，父节点的值总是大于它的子节点的值，在小根堆中，父节点的值总是小于它的子节点的值。

三、优先队列实现

我们可以使用一维数组来表示堆，如果一个节点的位置是index：

它的父节点的位置是(index-1)/2
它的左子节点的位置是2*index+1
它的右子节点的位置是2*index+2

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

  // 获取父节点的位置
  parent(index) {
    return Math.floor((index - 1) / 2);
  }

  // 获取左子节点的位置
  leftChild(index) {
    return 2 * index + 1;
  }

  // 获取右子节点的位置
  rightChild(index) {
    return 2 * index + 2;
  }

  // 交换两个元素的位置
  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }

  // 插入一个元素到堆中
  insert(value, priority) {
    const newNode = {value, priority};
    this.heap.push(newNode);
    this._heapifyUp();
  }

  // 弹出优先级最高的元素
  remove() {
    if (this.heap.length === 1) return this.heap.pop();
    const topPriority = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._heapifyDown();
    return topPriority;
  }

  // 获取优先级最高的元素
  peek() {
    return this.heap[0];
  }

  // 上移一个节点，维护堆的性质
  _heapifyUp() {
    let current = this.heap.length - 1;
    while (current > 0 && this.heap[current].priority > this.heap[this.parent(current)].priority) {
      this.swap(current, this.parent(current));
      current = this.parent(current);
    }
  }

  // 下移一个节点，维护堆的性质
  _heapifyDown() {
    let current = 0;
    let maxChildIndex = this.leftChild(current);
    while (maxChildIndex < this.heap.length) {
      if (this.rightChild(current)  this.heap[maxChildIndex].priority) {
        maxChildIndex = this.rightChild(current);
      }
      if (this.heap[current].priority >= this.heap[maxChildIndex].priority) break;
      this.swap(current, maxChildIndex);
      current = maxChildIndex;
      maxChildIndex = this.leftChild(current);
    }
  }
}

四、应用场景

优先队列的应用场景非常广泛，可以用来解决很多有优先级的问题。例如：

操作系统调度进程
任务调度
网络传输中的流量控制
负载均衡
数据压缩
Dijkstra算法
Huffman编码

五、总结

优先队列是一种很重要的数据结构，它的实现方法有很多种，其中使用堆结构的实现方法最高效。在实际应用中，优先队列可以帮助我们解决很多有优先级的问题，它的应用场景非常广泛。掌握优先队列的基本操作和实现方法，对于开发人员来说是十分重要的。

原创文章，作者：FUQFY，如若转载，请注明出处：https://www.506064.com/n/333758.html