Наихудшие случаи прогона косой кучи против левой кучи

Question

Я готовлюсь к нескольким техническим интервью и готовлюсь к слайдам лекций год или два назад о структурах данных.

Мне непонятно, почему в худшем случае время выполнения слияния для левой кучи равно O(log n), тогда как для косой кучи это O(n), когда косая куча по существу сливается так же, как левая куча.

Левая куча объединяет A и B, выбирая дерево с меньшим корнем и рекурсивно объединяя его правое поддерево с большим деревом. Затем он проверяет длину нулевого пути и меняет свои два поддерева, если он нарушает свойство левой структуры.

Косая куча делает то же самое, но слепо меняет свои два поддерева каждый раз, когда рекурсивно объединяет A и B.

Почему худшим случаем слияния для наклонной кучи станет O(n)? Это потому, что мы не можем гарантировать границу высоты, так как она рекурсивно сливается (так как она меняет стороны каждый раз)? Связано ли это с алгоритмом Флойда, что сумма высот от всех узлов в дереве растет в O(n)?

Answer 1

Левая куча имеет правильный путь длины не более log(N+1). В то время как правильный путь кучи может быть сколь угодно длинным (это может быть N). Поскольку производительность слияния зависит от длины правильного пути, поэтому время слияния в худшем случае выглядит следующим образом. Тем не менее, я не знаю, как косая куча находит. Можете ли вы привести какой-то особый случай, когда правильный путь косой кучи равен N?