computer-science - 比较两个二叉堆是否相等的最著名的界限是什么？

特别是在不修改输入的情况下。

到目前为止，我在这方面找不到任何东西，我想知道它是否有比明显的 O(n log n) 时间更好的解决方案。

标签： computer-sciencebinary-heap

根据您的定义，如果两个堆在重复提取最大元素时产生相同的元素序列，则它们是相等的。由于这相当于对堆中的元素进行破坏性排序，因此相等也等同于说两个堆元素序列在排序时是相等的。但这相当于两个堆之间的多集相等。

检查多集相等性可以在 O(n)（摊销）中完成，例如，通过使用哈希表将第一个堆的每个元素映射到其频率，这可以在 O(n) 中非破坏性地完成，然后检查第二个堆的元素针对哈希表，这也可以在 O(n) 中完成。

由于不考虑每个元素至少一次就不可能检查相等性，因此 O(n) 也是检查两个二叉堆相等性的最严格界限。