Ручная куча смещения массива

Question

Heapification массива с использованием siftdown - max (куча) это результат обмена 45 с 77, меня интересует следующий шаг, это 37, обмен с 77 или 45, замена с 67, учитывая, что эта ситуация была сделана путем замены 45 с 77, и я посмотрел на уровень 1 (уровень 0 37), мне нужно вернуться назад, чтобы исправить ситуацию с 45 и 67, или следует продолжить повышение, а затем исправить нижние числа? какая операция будет сделана первой в компьютерной реализации?

                            |37|  
            |77|                               |59|  
    |63|             |45|               |54|          |11|
|31|    |39|     |48|    |67|

Answer 1

Обычный способ сделать это здесь: http://en.wikipedia.org/wiki/Heapsort#Pseudocode.

Начните с индекса N / 2 (на диаграмме пробел, содержащий 45.) Сделайте siftDOWN.(Из вашего описания, похоже, вы сделали siftUP.) Если вы начали с этой диаграммы, вы бы сравнили 45 с ее дочерними (48,67) и поменялись местами 45 и 67. Затем вычли одно из индекса (item = 63)и сделай там ситдаун.Продолжайте, пока не дойдете до корня.Когда вы меняете своп с узлом, у которого есть свои дочерние элементы, вам также необходимо выполнить siftdown для этого узла.

Если вы выполните эту последовательность на диаграмме, вы увидите, что этот шаблон будет проверять вседерево.