Введение в программирование 5. Куча, бинарная куча, HeapSort

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

Лекция прочитана 30 сентября 2021 года
Лектор: Степанов Илья Даниилович
Оператор: Мария Шкатова
Монтаж: Жильцов Игорь

0:00 - Кучи
10:15 - Примеры использования
13:18 - Бинарная (двоичная) куча
22:50 - siftUp/siftDown - Вспомогательные процедуры
33:47 - Корректность siftUp и siftDown
50:36 - Реализация методов кучи
58:50 - HeapSort (Сортировка кучей)
1:01:50 - In-place HeapSort (без доп. памяти)
1:07:50 - Процедура Heapify
1:10:36 - Асимптотика Heapify

[dmitrydemis]

01:10:30 Здравствуйте, каким образом должна сработать функция siftDown for n to 1, если внутри while (2 * index < n) (где n - размер кучи с учётом одного пустого элемента для индексации с 1) почти всегда будет false? Что-то не вышло построить кучу

[renatxat]

Слишком абстрактное определение кучи, явно не для ознакомления лекция, а для повторения. Человек за барьером объясняет людям за барьером, как же там за барьером классно. В целом норм, но это именно та лекция, из-за которой я поплыл от барьера подальше.
Вот то, что не так очевидно из нумерации, но явно полезно понимать:
1) расстояния от корня до листьев ( количество вершин от самой верхней до какой-то из нижних) отличаются не более чем на 1
2) последний слой кучи заполняется слева направо
ИМХО