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

Question

У меня есть домашний вопрос, на котором написано:

Проблема 1: задан массив [22 | 25 | 71 | 24 | 18 | 5 | 27 | 32 | 104 | 8 | 23 | 66] Построить максимальная куча для массива. Показать все шаги, не пропуская ни одной детали.

Это моё понимание о максимальной куче от исследования в интернете:

Максимальная куча - это массив, который легче представить в виде двоичного дерева, где родительский узел всегда больше, чем его дочерние элементы, и «каждый раз, когда вы добавляете дочерний элемент, вы добавляете его слева, так что каждый раз, когда дерево увеличивается это высота, это полное дерево "

В любом случае это то, что я построил

Я думал, что это был правильный ответ, пока не прочитал вопрос 2 моей домашней работы, в котором говорилось:

Проблема 2: Используя тот же массив, что и в задаче 1, отсортируйте массив, используя Пирамидальная сортировка. Показать все шаги, не пропуская ни одной детали.

Теперь я в замешательстве. Может быть, я ответил на проблему № 2 ...

Answer 1

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

Идея состоит в том, что после построения кучи вы меняете последний и первый элемент в массиве, а затем работаете с тем же массивом, но только с использованием элементов 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.