Вы строите дерево, но не настраиваете свой массив. Массив отражает структуру кучи. Первый элемент является самым большим элементом в массиве, а следующие два элемента являются левым и правым дочерним элементом этого элемента.
Идея состоит в том, что после построения кучи вы меняете последний и первый элемент в массиве, а затем работаете с тем же массивом, но только с использованием элементов 0 ... array.size - 2. Условие кучи: неверно, и вы вызываете heapify, чтобы получить правильную структуру кучи для меньшего массива. Это снова дает вам самый большой элемент в этом меньшем массиве в первой позиции. Вы меняете первый и последний элемент в меньшем массиве и строите кучу в массиве, который имеет на 2 элемента меньше. Но у вас есть два элемента в конце, которые отсортированы (самый большой элемент из всего массива и следующий самый большой элемент (который является самым большим элементом из первого меньшего массива)). Вы будете делать это до тех пор, пока не получите массив rest, в котором не осталось элементов.
Взгляните на Диаграмма сортировки кучи в немецкой википедии . Сначала вы увидите несортированный массив. Меньший черный ящик указывает положение в массиве. Первое дерево - это куча.
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
Инвариант состоит в том, что ваше дерево представляет собой кучу до и после каждой итерации. Вот почему это работает. Потому что вы всегда поменяете местами самый большой элемент в конце массива heapified.