Почему siftDown лучше, чем siftUp в heapify?

Чтобы построить дерево кучи MAX, мы можем либо siftDown, либо siftUp, просеивая вниз, мы начинаем с корня и сравниваем его со своими двумя дочерними элементами, затем мы заменяем его более крупным элементом двух детей, если оба ребенка меньше, мы останавливаемся, в противном случае мы продолжаем просеивать этот элемент до тех пор, пока не достигнем листа node (или, разумеется, снова, пока этот элемент не станет больше, чем оба его дочерних элемента).

Теперь нам нужно будет сделать это n/2 раз, потому что количество листьев n/2, и листья будут удовлетворять свойству кучи, когда мы закончим измельчение последнего элемента на уровне до последнего (до листья) - поэтому мы оставим элементы n/2 для heapify.

Теперь, если мы используем siftUp, мы начнем с листьев, и в итоге нам нужно будет heapify все элементы n.

Мой вопрос: когда мы используем siftDown, мы не делаем в основном два сравнения (сравнивая элемент с его обоими дочерними элементами), а не только одно сравнение при использовании siftUp, поскольку мы сравниваем только этот элемент с его один родитель? Если да, разве это не означает, что мы удваиваем сложность и действительно заканчиваемся той же сложностью, что и просеивание?

Ответ 1

На самом деле, построение кучи с повторными вызовами siftDown имеет сложность O(n), тогда как построение его с повторными вызовами siftUp имеет сложность O(nlogn).

Это связано с тем, что при использовании siftDown время, затрачиваемое каждым вызовом , уменьшается с глубиной node, потому что эти узлы ближе к листьям. Когда вы используете siftUp, количество свопов увеличивается с глубиной node, потому что, если вы находитесь на полной глубине, вам, возможно, придется поменять место до корня. Поскольку число узлов растет экспоненциально с глубиной дерева, использование siftUp дает более дорогой алгоритм.

Кроме того, если вы используете Max-heap для сортировки, где вы нажимаете максимальный элемент кучи, а затем восстанавливаете его, проще сделать это, используя siftDown. Вы можете повторно выполнить обновление в O(logn) раз, поместив элемент max, поместив последний элемент в корневой каталог node (который был пуст, потому что вы его вытащили), а затем просеив его до самого правильного места.