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