偏斜堆与左堆的最坏情况运行时间
我正在为即将到来的一些技术面试做准备，并且刚刚复习了一两年前有关数据结构的讲座幻灯片。
我不清楚为什么左堆的合并的最坏情况运行时间是 O(log n)，而对于倾斜堆来说，它是 O(n)，当倾斜堆本质上以与左派堆相同的方式合并时。
左堆通过选取具有较小根的树并递归地将其右子树与较大的树合并来合并 A 和 B。然后，它检查空路径长度，如果违反左结构属性，则交换其两个子树。
倾斜堆做同样的事情，但每次递归合并 A 和 B 时都会盲目地交换它的两个子树。
为什么倾斜堆的合并的最坏情况会变成 O(n)？是因为我们无法保证递归合并时的高度限制（因为它每次都交换边）？这是否与弗洛伊德算法有关，即树中所有节点的高度总和以 O(n) 增长？
I'm studying for some technical interviews coming up and was just going over lecture slides from a year or two ago about data structures.
I'm not clear on why the worst case runtimes of merge for a leftist heap is O(log n) whereas for a skew heap it is O(n), when a skew heap essentially merges in the same way as a leftist heap.
A leftist heap merges A and B by picking the tree with the smaller root and recursively merging its right subtree with the larger tree. Then it checks the null path lengths and swaps its two subtrees if it violates leftist structure property.
A skew heap does the same thing but blindly swaps its two subtrees every time as it recursively merges A and B.
Why would the worst case of merge for a skew heap become O(n)? Is it because we can't guarantee a height bound as it recursively merges (since it's swapping sides every time)? Does this have to do with Floyd's Algorithm, that the sum of the heights from all nodes in a tree grows in O(n)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
左堆有一条长度最多为 log(N+1) 的右路径。而斜堆的右路径可以是任意长（可以是N）。由于合并的性能取决于正确路径的长度，因此最坏情况的合并时间是这样的。但是，我不知道倾斜堆是如何找到的。你能给我一些特殊情况，即倾斜堆的正确路径与N一样长吗？
leftist heap has a right path of length at most log(N+1). While skew heap's right path can be arbitrarily long(it can be N). Since the performance of merge depends on the length of the right path, so the worst-case merge times are like this. However, I don't know how skew heap does find. Can you give me some special case that the right path of skew heap is as long as N?