Куча - это двоичное дерево;следовательно, мы знаем, что он имеет log n глубины, и каждый уровень имеет 2 ^ i узлов.Уровень 0 (корневой) имеет 1 узел, уровень 1 имеет 2 узла, уровень 2 имеет 4 узла и т. Д.
Теперь подумайте о двух методах, которые вы упомянули:
Для восходящего,мы вставляем узлы в нижнюю часть и позволяем им «пузыриться» в куче каждый раз.Наоборот, для нисходящего, мы позволяем узлам «падать» на свое законное место.Какой из них более эффективен?
Давайте подумаем о наихудших сценариях:
В восходящем направлении каждый узел может подняться на самый верхний уровень.На уровне 1 для этого требуется один обмен (на два узла);на уровне 2 это требует двух (на четырех узлах) ... и как только мы доберемся до последнего уровня, мы должны сделать log n перестановок (на довольно больших n / 2 узлах)!Это дает нам эффективность O (n log n).
Сверху вниз: на каждом уровне любой узел может опуститься до нижней части дерева (log n swaps).Отличие снизу вверх заключается в том, что с увеличением максимального расстояния падения количество потенциальных узлов, на которые оно влияет, уменьшается.Уровень 0 является единственным, который может упасть в журнал n, и это только один узел (а не n / 2, как в восходящем).Следовательно, сумма всех «падений» равна O (n), и это более эффективный алгоритм.