Очередь с приоритетом

Очередь с приоритетом (priority queue) — абстрактная структура данных, из которой элемент извлекается не по порядку добавления (как в обычной очереди), а по наивысшему/наименьшему приоритету; обычно реализуется через Куча (Heap).

Зачем нужно

Обычная очередь не подходит, когда элементы имеют разный «вес» и важно всегда обрабатывать самый приоритетный. Очередь с приоритетом решает эту задачу за O(log n) на вставку и извлечение — намного лучше, чем O(n) при наивном поиске минимума в массиве. Это ключевая структура для алгоритмов Дейкстры, Прима и планировщиков.

Где используется

  • Алгоритм Дейкстры: всегда обрабатывать вершину с наименьшим расстоянием
  • Алгоритм Прима (MST): выбирать минимальное ребро
  • Планировщики задач ОС: выбирать задачу с наивысшим приоритетом
  • Медиана потока данных: два heap для поддержания медианы
  • Event-driven симуляции: обрабатывать события по времени

Основной контент

ADT Priority Queue

Операции:
- push(element, priority) — добавить элемент
- pop — извлечь элемент с наивысшим приоритетом
- peek — посмотреть без извлечения
- size — размер очереди

Реализация через min-heap

class PriorityQueue {
  #heap = ;

  #parent(i)    { return Math.floor((i - 1) / 2); }
  #left(i)      { return 2 * i + 1; }
  #right(i)     { return 2 * i + 2; }
  #swap(i, j)   { [this.#heap[i], this.#heap[j]] = [this.#heap[j], this.#heap[i]]; }
  #compare(i,j) { return this.#heap[i].priority - this.#heap[j].priority; }

  push(val, priority) {
    this.#heap.push({ val, priority });
    this.#bubbleUp(this.#heap.length - 1);
  }

  #bubbleUp(i) {
    while (i > 0 && this.#compare(i, this.#parent(i)) < 0) {
      this.#swap(i, this.#parent(i));
      i = this.#parent(i);
    }
  }

  pop {
    if (this.#heap.length === 1) return this.#heap.pop().val;
    const top = this.#heap[0].val;
    this.#heap[0] = this.#heap.pop();
    this.#siftDown(0);
    return top;
  }

  #siftDown(i) {
    const n = this.#heap.length;
    let min = i;
    const l = this.#left(i), r = this.#right(i);
    if (l < n && this.#compare(l, min) < 0) min = l;
    if (r < n && this.#compare(r, min) < 0) min = r;
    if (min !== i) { this.#swap(i, min); this.#siftDown(min); }
  }

  peek    { return this.#heap[0]?.val; }
  get size{ return this.#heap.length; }
}

const pq = new PriorityQueue();
pq.push('task-low', 10);
pq.push('task-high', 1);
pq.push('task-mid', 5);
console.log(pq.pop()); // 'task-high' (priority 1)
console.log(pq.pop()); // 'task-mid'  (priority 5)

Применение: k наименьших элементов

// Найти k наименьших элементов из n — O(n log k)
function kSmallest(arr, k) {
  // max-heap размером k
  const maxHeap = new PriorityQueue(); // с инвертированным приоритетом

  for (const num of arr) {
    maxHeap.push(num, -num); // инвертируем: меньший = выше приоритет → max-heap
    if (maxHeap.size > k) maxHeap.pop();
  }

  const result = ;
  while (maxHeap.size > 0) result.unshift(maxHeap.pop());
  return result;
}

Сравнение реализаций

Реализация push pop peek
Unsorted array O(1) O(n) O(n)
Sorted array O(n) O(1) O(1)
Binary heap O(log n) O(log n) O(1)
Fibonacci heap O(1) amort. O(log n) O(1)

В JavaScript нет встроенной PriorityQueue — необходимо реализовывать самостоятельно или использовать библиотеки (например, heap.js, @datastructures-js/priority-queue).

Частые ошибки

  • Реализовывать через Array.sort() после каждой вставки — O(n log n) вместо O(log n).
  • Не инвертировать приоритет при нужде в max-PQ через min-heap: используй -priority.
  • Путать PQ с обычной очередью: в очереди FIFO, в PQ — по приоритету.
  • Изменять приоритет элемента напрямую без обновления кучи — heap property нарушается.

Связанные темы

Ресурсы