Алгоритмы с нуля ALG · 08 · 03

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

АТД очередь с приоритетом: всегда извлекай элемент с наивысшим приоритетом. Реализация двоичная куча: insert и extractMin O(log n), peek O(1). Применение: планирование, Дейкстра, слияние потоков. Ключевое: АТД это контракт, куча это один способ его выполнить.

ALG ◷ 28 min

У вас есть куча. Теперь вы обёртываете её новым именем и обещанием: «Ты никогда не ищешь максимум или минимум. Ты всегда получаешь его за одну операцию — самый срочный, наиболее приоритетный, самый дешёвый элемент вперёд». Это обещание — очередь с приоритетом — не структура данных (это куча внизу), а контракт, что говорит, что можно делать. Куча — один способ держать этот контракт. Алгоритм Дейкстры её использует. Планировщики её используют. Каждый раз, когда нужно всегда обработать самую важную вещь следующей, ты берёшь очередь с приоритетом.

Цель

После этого урока ты можешь объяснить разницу между абстрактным типом данных и реализацией. Ты можешь назвать интерфейс очереди с приоритетом: insert новый элемент, extractMin (или extractMax) чтобы удалить и вернуть элемент с наивысшим приоритетом, и peek посмотреть его без удаления. Ты понимаешь, что двоичная куча — стандартная реализация и почему (O(log n) insert и extract, O(1) peek). Ты можешь узнать, когда задача требует очередь с приоритетом вместо обычной очереди или массива, и назвать три реальных применения: планирование задач, кратчайший путь Дейкстры и симуляция событий.

Идея

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

Очередь с приоритетом — это абстрактный тип данных — контракт, не конкретная структура данных. Описывает, что можно делать, а не как построено.

Контракт говорит: у тебя есть коллекция элементов, каждый с приоритетом (число или правило сравнения). Ты можешь:

Insert (вставить) новый элемент.
ExtractMin (или extractMax): удалить и вернуть элемент с наименьшим (или наибольшим) приоритетом.
Peek (подглядеть): посмотреть элемент с наивысшим приоритетом без удаления.

Вот интерфейс. Куча живёт внизу.

АТД против реализации

Абстрактный тип данных (АТД) — это спецификация — контракт. Говорит, какие операции поддерживаются и что они делают. НЕ говорит как.

Очередь с приоритетом — это АТД. Её операции: insert, extractMin и peek.

Реализация — это код. Двоичная куча — одна частая реализация: использует полное двоичное дерево, хранящееся в массиве, со свойством мин-кучи (каждый родитель ≤ дети).

Один АТД может иметь много реализаций. Очередь с приоритетом может быть:

Двоичной кучей (быстрый insert и extract, эффективна по памяти).
Отсортированным массивом (быстрый peek, медленный insert и extract).
Связным списком (медленно всё).
Сбалансированным двоичным деревом поиска вроде красно-чёрного дерева (log n все операции, но больше констант).

Вместе эти варианты делают компромисс очевидным: куча побеждает, потому что балансирует все три операции и умещается в плоский массив. Если когда-нибудь перейдёшь на кучу Фибоначчи или bucket queue — клиентский код не изменится, в этом и смысл АТД.

Когда кодишь, используешь абстракцию АТД. Спрашиваешь: insert, extractMin, peek. Реализация заменяема — поменяй её, клиентский код не изменится.

Почему двоичная куча?

Двоичная куча — стандартная реализация, потому что быстра (O(log n) insert и extract, O(1) peek) и памяти эффективна (нет указателей, просто массив). Простая настолько, чтобы написать руками, но боевая.

Мин-куча против макс-кучи

В мин-куче extractMin возвращает наименьший элемент. Используется когда хочешь обработать наименьшую стоимость, кратчайшее время или наименее срочную задачу первой.

В макс-куче extractMax возвращает наибольший элемент. Используется когда хочешь наивысший приоритет, наибольший вес или самую срочную задачу первой.

Логика симметрична — если нужна макс-куча и есть только мин-куча библиотека, инвертируй приоритеты и используй мин-кучу.

Интерфейс очереди с приоритетом в псевдокоде

PriorityQueue:
  insert(element, priority)
    Добавь элемент в очередь.
  
  extractMin()
    Удали и верни элемент с наименьшим приоритетом.
  
  peek()
    Верни (без удаления) элемент с наименьшим приоритетом.
  
  isEmpty()
    Истина если очередь пуста.
  
  size()
    Количество элементов в очереди.

Пример: планирование задач

У тебя есть очередь задач. Каждая задача имеет приоритет (1 = срочно, 10 = низкий приоритет). Задачи приходят в случайные моменты. Ты хочешь всегда работать над самой срочной задачей следующей.

Queue: [print job (приоритет 3), compile (приоритет 5), test (приоритет 1)]

extractMin() → test с приоритетом 1 (хотя добавлена последней)
insert(deploy, приоритет 2)

Queue: [deploy (приоритет 2), print job (приоритет 3), compile (приоритет 5)]

extractMin() → deploy с приоритетом 2

Обычная очередь (FIFO) здесь не работает — заставила бы делать print job первой, потом compile, тратя время на низкоприоритетную работу.

Вставляй в любом порядке; удаляй по приоритету. Куча переупорядочивает внутри так, что extractMin всегда возвращает элемент с наименьшим приоритетом. Порядок прихода (compile, deploy, test, doc) не совпадает с порядком выхода (deploy, test, compile, doc) — приоритет решает, кто уходит первым.

Код

Интерфейс очереди с приоритетом в коде

1 class MinPriorityQueue {

2 constructor() {

3 this.heap = [];

4 }

6 // Вставь элемент со значением (меньше = выше приоритет)

7 insert(element, value) {

8 this.heap.push({ element, value });

9 this.siftUp(this.heap.length - 1);

10 }

12 // Удали и верни элемент с наименьшим значением

13 extractMin() {

14 const root = this.heap[0];

15 this.heap[0] = this.heap[this.heap.length - 1];

16 this.heap.pop();

17 if (this.heap.length > 0) {

18 this.siftDown(0);

19 }

20 return root.element;

21 }

23 // Подглядни элемент с наименьшим значением без удаления

24 peek() {

25 return this.heap.length > 0 ? this.heap[0].element : null;

26 }

28 // Проверь если пуста

29 isEmpty() {

30 return this.heap.length === 0;

31 }

33 // Количество элементов

34 size() {

35 return this.heap.length;

36 }

38 // Просей вверх чтобы восстановить свойство кучи после вставки

39 siftUp(index) {

40 while (index > 0) {

41 const parentIndex = Math.floor((index - 1) / 2);

42 if (this.heap[index].value < this.heap[parentIndex].value) {

43 [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];

44 index = parentIndex;

45 } else {

46 break;

47 }

48 }

49 }

51 // Просей вниз чтобы восстановить свойство кучи после удаления

52 siftDown(index) {

53 while (true) {

54 const left = 2 * index + 1;

55 const right = 2 * index + 2;

56 let smallest = index;

58 if (left < this.heap.length && this.heap[left].value < this.heap[smallest].value) {

59 smallest = left;

60 }

61 if (right < this.heap.length && this.heap[right].value < this.heap[smallest].value) {

62 smallest = right;

63 }

65 if (smallest !== index) {

66 [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];

67 index = smallest;

68 } else {

69 break;

70 }

71 }

72 }

73 }

L1 MinPriorityQueue обёртывает массив кучи.
L5 Вставь элемент с приоритет значением. Меньше значение = выше приоритет.
L9 extractMin удаляет и возвращает элемент с наименьшим значением (корень мин-кучи).
L17 peek возвращает элемент с наименьшим значением без удаления.
L29 siftUp восстанавливает свойство кучи после вставки, двигая элемент вверх.
L39 siftDown восстанавливает свойство кучи после удаления, двигая элемент вниз.

Использование очереди с приоритетом

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

insert(element, value) {
  this.heap.push({ element, value });
  this.siftUp(this.heap.length - 1);
}

extractMin() {
  const root = this.heap[0];
  this.heap[0] = this.heap[this.heap.length - 1];
  this.heap.pop();
  if (this.heap.length > 0) {
    this.siftDown(0);
  }
  return root.element;
}

peek() {
  return this.heap.length > 0 ? this.heap[0].element : null;
}

isEmpty() {
  return this.heap.length === 0;
}

siftUp(index) {
  while (index > 0) {
    const parentIndex = Math.floor((index - 1) / 2);
    if (this.heap[index].value < this.heap[parentIndex].value) {
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    } else {
      break;
    }
  }
}

siftDown(index) {
  while (true) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;

if (left < this.heap.length && this.heap[left].value < this.heap[smallest].value) {
      smallest = left;
    }
    if (right < this.heap.length && this.heap[right].value < this.heap[smallest].value) {
      smallest = right;
    }

if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    } else {
      break;
    }
  }
}
}

// Пример планирования задач
const pq = new MinPriorityQueue();

// Добавь задачи с приоритетами (меньше число = выше приоритет)
pq.insert("compile", 5);
pq.insert("deploy", 2);
pq.insert("test", 3);
pq.insert("documentation", 7);

console.log("Обрабатываем задачи в порядке приоритета:");
while (!pq.isEmpty()) {
const task = pq.extractMin();
console.log("Выполняю:", task);
}

// Посмотри что следующее без удаления
const pq2 = new MinPriorityQueue();
pq2.insert("urgent", 1);
pq2.insert("normal", 5);
console.log("Следующая задача:", pq2.peek());

Output

Пошаговый разбор

1 const pq = new MinPriorityQueue();

2 pq.insert('task1', 5);

3 pq.insert('task2', 2);

4 pq.insert('task3', 1);

1 const pq = new MinPriorityQueue();

2 // После вставок: куча имеет [(task3,1), (task1,5), (task2,2)]

3 const extracted = pq.extractMin();

Сложность

Операции очереди с приоритетом с использованием двоичной кучи

Insert: Добавляет новый элемент и вызывает просей вверх. Просей вверх двигает элемент вверх один уровень за обмен, и куча с n элементами имеет высоту O(log n).

Время: O(log n)

ExtractMin: Удаляет корень, двигает последний элемент в корень и вызывает просей вниз. Просей вниз тоже берёт O(log n).

Время: O(log n)

Peek: Возвращает корень за один доступ к массиву.

Время: O(1)

IsEmpty и size: Проверяют длину массива.

Время: O(1)

Почему не другие реализации?

Отсортированный массив может дать O(1) peek, но insert и extract требуют сдвига O(n) элементов — O(n) за операцию.

Неотсортированный массив дает O(1) insert, но extractMin требует сканирования всех элементов чтобы найти наименьший — O(n) за операцию.

Связный список это O(n) за всё.

Двоичная куча балансирует все три: O(log n) insert и extract, O(1) peek. Поэтому стандартный выбор для очередей с приоритетом.

Пространственная сложность

Куча использует один массив, так что пространство это O(n) для n элементов.

Практика 0 / 6

В очереди с приоритетом на основе двоичной мин-кучи, какая операция гарантировано O(1)?

Ты строишь планировщик задач. Задачи имеют приоритеты (меньше число = срочнее). Ты хочешь всегда выполнить самую срочную задачу следующей. Что использовать?

Какая разница между абстрактным типом данных (АТД) и реализацией?

В алгоритме кратчайшего пути Дейкстры, нужно повторно извлекать вершину с наименьшим расстоянием. Какая это структура данных?

Куча с приоритетом мин-кучи имеет 8 элементов. Сколько шагов (сравнений и обменов) extractMin берёт в худшем случае?

Нужно слить 4 отсортированные списки в один отсортированный список. Какой подход использует очередь с приоритетом?

▸lesson.inset.undefined

Почему очереди с приоритетом имеют значение. Любая реальная система с задачами, событиями или запросами имеет приоритеты. Веб-сервер имеет запросы от пользователей; некоторые важнее (платящие клиенты первыми). Робот имеет датчики и исполнительные элементы; срочные события безопасности имеют приоритет. Больница имеет пациентов в очереди; критические случаи видены первыми. Без очереди с приоритетом, ты или обрабатываешь вещи случайно (несправедливо, неэффективно) или вручную ищешь самую важную вещь (медленно, O(n)). Очередь с приоритетом решает оба: всегда дай мне самую важную вещь, быстро.

▸lesson.inset.undefined

Смешивание АТД и реализации. Очередь с приоритетом это НЕ куча. Куча это один способ реализовать очередь с приоритетом. Если кто-то спросит «Является ли очередь с приоритетом кучей?», ответ это «Нет, очередь с приоритетом это АТД; куча это реализация этого АТД.» Это отличие имеет значение, потому что на интервью ты можешь сказать «Я буду использовать очередь с приоритетом, поддержанную кучей» чтобы понятно показать, что ты думаешь обоих уровнях.

▸lesson.inset.undefined

Понижение приоритета. Некоторые проблемы с очередью с приоритетом (вроде Дейкстры) нужно понизить приоритет элемента после вставки. Двоичная куча это не поддерживает напрямую — пришлось бы перестроить или использовать более сложную реализацию (куча Фибоначчи, или вставить заново с новым приоритетом и пропустить старый). Для этого урока, предполагаем простую очередь с приоритетом что поддерживает только insert, extractMin и peek.

Проверь себя

Викторина

Объясни отношение между очередью с приоритетом (АТД) и двоичной кучей (реализация). Какие операции должен поддерживать АТД и почему куча хороший выбор?

Итог

Очередь с приоритетом это абстрактный тип данных — контракт, что обещает три операции: insert новый элемент, extractMin чтобы удалить и вернуть элемент с наивысшим приоритетом, и peek чтобы посмотреть элемент с наивысшим приоритетом без удаления. Двоичная куча это стандартная реализация, дающая O(log n) insert и extract, O(1) peek. Понимай разницу: АТД это интерфейс; реализация это код. Очередь с приоритетом это не FIFO очередь и не LIFO стек — она всегда дает тебе самую важную вещь следующей. Используй очередь с приоритетом когда нужно всегда обрабатывать самый срочный элемент: планирование задач, кратчайший путь Дейкстры, симуляция событий, слияние отсортированных потоков. Следующее: Урок 04 применяет очередь с приоритетом к проблемам top-K, и урок 05 показывает k-way merge. Теперь, когда тянешься за отсортированным списком чтобы «всегда обрабатывать самое срочное», спроси себя сначала: не решает ли это очередь с приоритетом за O(log n) вместо O(n)?

Практика

Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.

вспомнитьприменитьуглубить0 из 4 завершено

Что-то непонятно?

Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.

Примени это

Примени этот урок в реальном проекте.

Движок поиска маршрутовЧетыре алгоритма поиска — одна общая задача: добраться из A в B по взвешенной сетке. Ты построишь BFS, DFS, Dijkstra и A* на одной модели графа, а затем запустишь их бок о бок и увидишь, как они расходятся: DFS бросается в тупик, BFS равномерно растекается, Dijkstra ползёт наружу по стоимости, A* тянется к цели. Именно здесь раздел про алгоритмы перестаёт быть набором фактов и становится инструментами, между которыми ты выбираешь осознанно.