Задача алгоритма Max-Heapify

Question

Пусть A [1 ... 9] = 3 9 5 4 8 6 11 7 2 - массив, состоящий из 9 чисел. Проиллюстрируйте, как выглядит A после выполнения кода Max - Heapify (A, 4, 9), Max-Heapify (A, 3,9), Max-Heapify (A, 2,9), Max-Heapify (A, 1, 9. *

Heapify (A, 4, 9) значение 4 и 2 обмениваются 3 9 5 2 8 6 11 7 4 -> I отсортировано 3 9 5 7 8 6 11 2 4

Max-Heapify (A , 3,9) -> обмен значениями 5 и 4

3 9 4 7 8 6 11 2 5 -> I сортировка 3 9 11 7 8 6 4 2 5 -> 11 9 3 7 8 6 4 2 5

Макс. Heapify (A, 2,9) -> обмен значениями 11 и 9

11 9 6 7 8 3 4 2 5

Макс. Heapify (A , 1,9) -> значение 11 и 5 5 9 6 7 8 3 4 2 11 -> Как мне отсортировать его, начиная с родительского узла или снизу вверх? Есть ли какие-либо советы по решению этой проблемы в целом в массиве вместо рисования дерева кучи?

РЕШЕНИЕ: 11 9 6 7 8 3 5 4 2

Answer 1

Каким-то образом вы интерпретируете MaxHeapify как что-то другое, чем предполагается. Например, вы пишете:

Heapify (A, 4, 9) значение 4 и 2 обмен

Нет. Дочерние элементы значения в индексе 4 находятся в индексах 8 и 9. Чтобы узнать, где находятся дочерние элементы узла, удвойте индекс и добавьте 0 или 1. 7 в (индекс 8) больше, чем его родитель в индексе 4, поэтому обмен между значениями 4 и 7. Результат:

3 9 5 7 8 6 11 4 2
      *        * *

Обратите внимание, что после этого обмена оба дочерних элемента узла с индексом 4 будут меньше.

Heapify (A, 3, 9) будет сравниваться значение в индексе 3 (5) с дочерними элементами в индексах 6 и 7. Значения 6 и 11: 11 должны всплыть:

3 9 11 7 8 6 5 4 2
     *     * *

Heapify (A, 2, 9) будет сравнивать значение в индексе 2 ( 9) с дочерними индексами 4 и 5: значения 7 и 8: все нормально, как есть; без изменений:

3 9 11 7 8 6 5 4 2
  *    * *

Heapify (A, 1, 9) будет сравнивать значение по индексу 1 (3) со своими потомками по индексам 2 и 3: значения 9 и 11: 11 должны всплыть:

11 9 3 7 8 6 5 4 2
*  * *

На этом этапе куча полностью накапливается: для каждого имеющегося у вас узла его значение больше (или равно), чем значения его дочерних элементов. Это все куча. Куча - это не отсортированный массив. Чтобы получить значения в порядке убывания, вам нужно вытолкнуть элементы из верхней части кучи в соответствии с алгоритмом extract : выньте передний элемент, поместите туда элемент tail, сделайте элемент массива 1 короче и просеять переднее значение в кучу (через обмены), пока не восстановится свойство кучи.

Вы можете прочитать обо всех функциях, связанных со структурой кучи, в Wikipedia .