1

我正在为即将到来的一些技术面试而学习，并且正在阅读一两年前有关数据结构的演讲幻灯片。

我不清楚为什么左倾堆的最坏情况合并运行时间是 O(log n) 而对于倾斜堆它是 O(n)，当倾斜堆基本上以与左倾堆相同的方式合并时。

左派堆通过选择具有较小根的树并递归地将其右子树与较大的树合并来合并 A 和 B。然后它检查空路径长度，如果它违反左派结构属性，则交换它的两个子树。

倾斜堆做同样的事情，但每次递归合并 A 和 B 时都会盲目地交换它的两个子树。

为什么倾斜堆合并的最坏情况会变成 O(n)？是因为我们不能保证递归合并时的高度限制（因为它每次都在交换边）？这是否与弗洛伊德算法有关，即树中所有节点的高度之和以 O(n) 增长？

4

1 回答 1

1

左派堆的右路径长度最多为 log(N+1)。而倾斜堆的正确路径可以任意长（可以是N）。由于合并的性能取决于正确路径的长度，所以最坏情况的合并时间是这样的。但是，我不知道倾斜堆是如何找到的。您能给我一些特殊情况，即倾斜堆的正确路径与 N 一样长吗？

于 2011-01-04T06:43:15.660 回答