Heap Sort — это улучшенная сортировка выбором, основанная на (max) структуре данных Heap;
Он делит элементы на две части (сортированные и несортированные). Heap Sort итеративно уменьшает несортированную часть, удаляя элемент «max» и перемещая его к отсортированному до тех пор, пока несортированная часть не станет пустой.
Сначала создайте Max Heap: