Проверяет понимание структуры данных «очередь с приоритетом», её свойств и способов реализации, что важно для алгоритмических задач и систем с планированием задач.
Очередь с приоритетом — это абстрактная структура данных, которая хранит элементы с присвоенными им приоритетами. В отличие от обычной очереди (FIFO), извлечение элемента происходит не по времени добавления, а по значению приоритета: всегда достаётся элемент с максимальным (или минимальным) приоритетом. Это ключевое отличие, которое делает её незаменимой в задачах планирования, поиска кратчайших путей (алгоритм Дейкстры) и обработки событий.
В идеальной реализации обе основные операции (вставка и извлечение) выполняются за O(log n), где n — количество элементов.
Самый распространённый способ — бинарная куча. Это полное бинарное дерево, которое хранится в массиве. Для max-heap каждый родитель больше или равен своих детей. Благодаря этому корень всегда содержит максимальный элемент. Вставка происходит путём добавления элемента в конец массива и последующего «всплытия» (sift-up) до восстановления свойства кучи. Извлечение — замена корня последним элементом и «просеивание» вниз (sift-down).
class MaxHeap {
constructor() { this.heap = []; }
insert(val) {
this.heap.push(val);
this._siftUp(this.heap.length - 1);
}
extractMax() {
if (this.heap.length === 0) return null;
const max = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this._siftDown(0);
}
return max;
}
_siftUp(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.heap[parent] < this.heap[i]) {
[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
i = parent;
} else break;
}
}
_siftDown(i) {
const n = this.heap.length;
while (true) {
let largest = i;
const left = 2 * i + 1, right = 2 * i + 2;
if (left < n && this.heap[left] > this.heap[largest]) largest = left;
if (right < n && this.heap[right] > this.heap[largest]) largest = right;
if (largest !== i) {
[this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
i = largest;
} else break;
}
}
}Очередь с приоритетом используется в алгоритме Дейкстры для поиска кратчайшего пути, в планировщиках задач операционных систем, в системах обработки событий (например, в игровых движках), а также в алгоритмах сжатия данных (код Хаффмана).
Итог: Очередь с приоритетом — фундаментальная структура данных, которую стоит знать каждому разработчику. Бинарная куча — оптимальный баланс между простотой и производительностью, поэтому её реализация — стандартный ответ на собеседовании.
