Алгоритмы с нуля

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

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

◷ 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 все операции, но больше констант).

Когда кодишь, используешь абстракцию АТД. Спрашиваешь: 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, тратя время на низкоприоритетную работу.

Код

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


      1
      class MinPriorityQueue {
    

      2
      constructor() {
    

      3
        this.heap = [];
    

      4
      }
    

      5
       
    

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

      7
      insert(element, value) {
    

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

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

      10
      }
    

      11
       
    

      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
      }
    

      22
       
    

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

      24
      peek() {
    

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

      26
      }
    

      27
       
    

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

      29
      isEmpty() {
    

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

      31
      }
    

      32
       
    

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

      34
      size() {
    

      35
        return this.heap.length;
    

      36
      }
    

      37
       
    

      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
      }
    

      50
       
    

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

      52
      siftDown(index) {
    

      53
        while (true) {
    

      54
          const left = 2 * index + 1;
    

      55
          const right = 2 * index + 2;
    

      56
          let smallest = index;
    

      57
       
    

      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
          }
    

      64
       
    

      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.

Продолжить восхождение ↑Топ-K и k-й по величине элемент