Heaps и priority queues

Heap поддерживает partial order: минимум или максимум легко извлечь, но вся структура не sorted. Priority queue является интерфейсом, heap - частая реализация. Они полезны для top-k, scheduling, merge-k-lists и shortest-path algorithms.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Ожидайте вопросы про push/pop complexity, почему sorting всех values расточителен для top-k и почему Dijkstra требует priority по current distance.

Типовые ошибки: В JavaScript нет built-in heap, поэтому опишите data structure или используйте маленькую реализацию. Помните, что peek O(1), а insert и remove O(log n).

Чеклист:

• Отличайте heap от sorted array.
• Используйте top-k, когда k мал.
• Назовите O(log n) updates.
• Уточните min-heap или max-heap.