Алгоритмы с нуля
Heap: свободное припоминание
Припоминание сильнее перечитывания. Для каждой подсказки скажите или запишите полный ответ по памяти, прежде чем открыть эталон — именно усилие припоминания закрепляет модель heap.
Восстановите стержень юнита, не подглядывая: двусоставный инвариант heap, аргумент O(n) для build-heap, контракт priority queue, приём «heap размера k» для top-k и k-way merge и то, как heap-sort вытекает из pop.
- 01Назовите два свойства, определяющие binary heap, и объясните, почему они позволяют хранить его как плоский массив без указателей.
- 02Пройдите push и pop и объясните, почему каждая операция есть O(log n).
- 03Почему build-heap есть O(n), а вставка n элементов по одному — O(n log n)?
- 04Различите ADT priority queue и binary heap и назовите, когда различие меняет проект.
- 05Объясните приём «heap размера k» и как одна идея решает и top-k, и k-way merge.
- 06Как heap-sort вытекает из операций heap и каковы его время и память?
Если вы восстановили каждый ответ по памяти, у вас есть стержень юнита: пара «полнота + свойство heap» даёт массив без указателей и peek за O(1); sift-up/sift-down дают push/pop за O(log n); build-heap достигает O(n), взвешивая стоимость по высоте узла; контракт PQ отделён от heap, его реализующего; heap размера k превращается в top-k (min-heap, вытеснить корень) и k-way merge (по одному кандидату от списка, продвижение по индексу); а heap-sort — это просто build-heap плюс повторный pop, гарантированный O(n log n), память O(1).