Создайте максимальную кучу для массива

Вы строите дерево, но не настраиваете свой массив. Массив отражает структуру кучи. Первый элемент является самым большим элементом в массиве, а следующие два элемента являются левым и правым дочерними элементами этого элемента.

Идея состоит в том, что после создания кучи вы меняете местами последний и первый элемент в массиве, а затем работаете с тем же массивом, но только с использованием элементов 0 ... array.size - 2. Условие кучи недопустимо, и вы вызовите heapify, чтобы получить правильную структуру кучи для меньшего массива. Это снова дает вам самый большой элемент в этом меньшем массиве в первой позиции. Вы меняете местами первый и последний элемент в меньшем массиве и строите кучу на массиве, который имеет на 2 элемента меньше. Но у вас есть два элемента в конце, которые отсортированы (самый большой элемент из всего массива и следующий по величине элемент (который является самым большим элементом из первого меньшего массива)). Вы будете делать это до тех пор, пока у вас не будет оставшегося массива, в котором не осталось элементов.

Взгляните на схему сортировки кучей в немецкой Википедии. Сначала вы увидите несортированный массив. Меньшее черное поле указывает положение в массиве. Первое дерево — куча.

 Unsorted array
 23 | 1 | 6 | 19 | 14 | 18 | 8 | 24 | 15

 Heapified Array
 24 | 23 | 18 | 19 | 14 | 8 | 6 | 1 | 15

 First iteration
 Swap First (Biggest Element in Array) with last Element (could be anything)
 15 | 23 | 18 | 19 | 14 | 8 | 6 | 1 | 24

 heap condition is invalid

 Build heap on array.size - 2
 23 | 19 | 18 | 15 | 14 | 8 | 6 | 1 || 24

 Swap first and last element in smaller heap
 1 | 19 | 18 | 15 | 14 | 8 | 6 | 23 || 24

 Build heap on array.size - 3
 19 | 15 | 18 | 1 | 14 | 8 | 6 || 23 | 24

 Swap first and last element on that smaller heap and build heap on array.size - 4
 until you cant shrink the heap anymore, you'll receive
 || 1 | 8 | 14 | 15 | 18 | 19 | 23 | 24

Инвариант заключается в том, что ваше дерево представляет собой кучу до и после каждой итерации. Вот почему это работает. Потому что вы всегда будете заменять самый большой элемент на конец массива с кучей.