Что такое 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/max | O(1) |
| push | O(log n) |
| pop | O(log n) |
| build heap | O(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).