re:re:actable
Урок 064 минуты чтения

Что такое heap и priority queue?

На этой странице
Кратко

Priority queue возвращает элемент с наивысшим приоритетом, а heap - популярная структура для ее реализации. В JavaScript нет встроенной priority queue, поэтому на интервью ее часто реализуют через binary heap.

Вопрос

Что такое heap и priority queue и как их реализовать в JavaScript?

Что такое priority queue?

Обычная очередь отдает самый старый элемент.

Priority queue отдает самый важный элемент.

Примеры:

  • ближайшая вершина в Dijkstra;
  • top K элементов;
  • планировщик задач;
  • merge K sorted lists;
  • медиана потока.

Min heap

В min heap родитель меньше или равен детям:

        1
      /   \
     3     5
    / \
   7   9

Минимум всегда в корне. При этом куча не отсортирована целиком: 7 и 9 стоят ниже 3, но сравнивать 5 с 7 не нужно - правило действует только между родителем и детьми. Именно поэтому поддерживать кучу дешевле, чем отсортированный массив.

Индексы в массиве

Дерево хранят в обычном массиве, по уровням слева направо:

индекс:  0  1  2  3  4
heap:   [1, 3, 5, 7, 9]
 
1 (0) - корень; его дети 3 (1) и 5 (2); дети 3 - это 7 (3) и 9 (4)

Для элемента i:

const parent = Math.floor((i - 1) / 2)
const left = 2 * i + 1
const right = 2 * i + 2

Минимальная реализация

class MinHeap {
  private heap: number[] = []
 
  get size(): number {
    return this.heap.length
  }
 
  peek(): number | undefined {
    return this.heap[0]
  }
 
  push(value: number): void {
    this.heap.push(value)
    this.bubbleUp(this.heap.length - 1)
  }
 
  pop(): number | undefined {
    if (this.heap.length === 0) return undefined
    if (this.heap.length === 1) return this.heap.pop()
 
    const root = this.heap[0]
    this.heap[0] = this.heap.pop()!
    this.bubbleDown(0)
    return root
  }
 
  private bubbleUp(index: number): void {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2)
      if (this.heap[parent] <= this.heap[index]) break
      ;[this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]]
      index = parent
    }
  }
 
  private bubbleDown(index: number): void {
    while (true) {
      let smallest = index
      const left = 2 * index + 1
      const right = 2 * index + 2
 
      if (left < this.heap.length && this.heap[left] < this.heap[smallest]) smallest = left
      if (right < this.heap.length && this.heap[right] < this.heap[smallest]) smallest = right
      if (smallest === index) break
 
      ;[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]]
      index = smallest
    }
  }
}

Как это работает: push и pop

push(2) в кучу [1, 3, 5, 7, 9]: кладем в конец и "всплываем" (bubble up), пока родитель больше.

[1, 3, 5, 7, 9, 2]   2 на индексе 5, родитель - индекс 2 (5). 5 > 2 - меняем
[1, 3, 2, 7, 9, 5]   2 на индексе 2, родитель - индекс 0 (1). 1 < 2 - стоп

pop(): забираем корень 1, на его место ставим последний элемент и "топим" (bubble down), меняя с меньшим из детей.

[5, 3, 2, 7, 9]   корень 5, дети 3 и 2. Меньший - 2, меняем
[2, 3, 5, 7, 9]   5 на индексе 2, детей нет - стоп. pop вернул 1

Каждое всплытие или погружение проходит максимум высоту дерева, а высота почти полного дерева - log n. Отсюда O(log n) для push и pop.

Сложности

ОперацияСложность
peek min/maxO(1)
pushO(log n)
popO(log n)
build heapO(n)

Что отвечать на собеседовании?

Heap - почти полное бинарное дерево, часто хранимое в массиве. Оно позволяет быстро получить минимум или максимум. Priority queue на heap дает push и pop за O(log n), peek за O(1). В JS встроенной priority queue нет, поэтому для задач top K или Dijkstra ее реализуют вручную или используют библиотеку.

Что важно помнить: частые ошибки

  • Путать heap и binary search tree.
  • Думать, что heap полностью отсортирован.
  • Забывать bubble up/down.
  • Ошибаться в индексах parent/children.
  • Использовать сортировку после каждого push.

Мини-шпаргалка

  • Heap дает быстрый min/max.
  • Min heap - минимум в корне.
  • Хранится в массиве.
  • Parent: (i - 1) / 2.
  • Children: 2i + 1, 2i + 2.
  • Push/pop - O(log n).

Документация

Wikipedia: Binary heap, VisuAlgo: Binary Heap.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам