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

Question

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

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

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

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

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

Answer 1

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