Implementation (Part 1)
Урок 5 из 9 курса Пирамидальная сортировка — Серия DSA на Coddy.
Мы построим пирамидальную сортировку (Heap Sort), начиная с её основной операции.
Задание
ЛегкоСердцем пирамидальной сортировки (Heap Sort) является операция sift-down (просеивание вниз). Давайте сначала реализуем её.
Напишите функцию с именем siftDown, которая принимает массив arr (рассматриваемый как бинарная куча) и индекс i, и восстанавливает свойство max-heap (максимальной кучи) в этом узле, перемещая его вниз. Сравните узел с двумя его дочерними элементами по индексам 2*i + 1 и 2*i + 2; если больший из дочерних элементов больше текущего узла, поменяйте их местами и продолжайте процесс с позиции дочернего элемента. Верните массив.
Например, siftDown([1, 10, 5, 3, 2], 0) возвращает [10, 3, 5, 1, 2].
Попробуйте сами
#include <stdlib.h>
int* siftDown(int* arr, int arr_size, int i, int* returnSize) {
// Напишите код здесь
*returnSize = arr_size;
return arr;
}
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Пирамидальная сортировка — Серия DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity