Расскажите про очередь с приоритетом

Что такое очередь с приоритетом

Очередь с приоритетом — это абстрактная структура данных, которая поддерживает две основные операции: добавление элемента с некоторым приоритетом и извлечение элемента с максимальным (или минимальным) приоритетом. В отличие от обычной очереди (FIFO), порядок извлечения определяется не временем добавления, а значением приоритета. Это позволяет эффективно обрабатывать задачи, где важнее срочность или важность, а не порядок поступления.

Как это работает

Наиболее распространённая реализация — бинарная куча (binary heap). Куча — это полное бинарное дерево, где каждый родитель имеет приоритет выше (для max-heap) или ниже (для min-heap), чем его дети. Благодаря этому свойству корень всегда содержит элемент с экстремальным приоритетом. Вставка и удаление корня выполняются за O(log n), так как требуется восстановить свойство кучи после изменения.

Пример на JavaScript с использованием массива и ручной реализации min-heap:

class MinHeap {
  constructor() { this.heap = []; }
  push(val) {
    this.heap.push(val);
    this._bubbleUp(this.heap.length - 1);
  }
  pop() {
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._sinkDown(0);
    }
    return min;
  }
  _bubbleUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[i] < this.heap[parent]) {
        [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
        i = parent;
      } else break;
    }
  }
  _sinkDown(i) {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1, right = 2 * i + 2;
      if (left < n && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < n && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest !== i) {
        [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
        i = smallest;
      } else break;
    }
  }
}
// Использование:
const pq = new MinHeap();
pq.push(5); pq.push(2); pq.push(8);
console.log(pq.pop()); // 2

Где применяется

• Алгоритм Дейкстры для поиска кратчайшего пути — извлечение вершины с минимальным расстоянием.
• Планировщики задач в операционных системах — выбор процесса с наивысшим приоритетом.
• Обработка событий в симуляциях — следующее событие с наименьшим временем.
• Сжатие данных (алгоритм Хаффмана) — построение дерева на основе частот.

Вывод

Очередь с приоритетом — незаменимый инструмент для задач, где требуется быстрый доступ к экстремальному элементу среди динамически меняющегося набора. Её использование позволяет снизить сложность алгоритмов с O(n) до O(log n) на операцию, что критично для больших объёмов данных. Знание этой структуры важно для любого разработчика, работающего с алгоритмами или системами реального времени.