不修改输入时，比较两个二叉堆相等性的最优已知边界是什么？

这是个挺容易被堆的“优先级特性”误导的问题，很多人第一反应会想到弹出堆顶的O(n log n)解法，但其实在不修改输入的前提下，我们有更优的方案，甚至是线性时间的最优解。咱们分两种最常见的“相等性”定义来具体说：

场景1：判断两个堆的元素多重集合完全相等（不关心堆结构） #

这种情况的最优解法是O(n)时间，比O(n log n)高效得多：

• 遍历第一个堆的所有元素：因为二叉堆是完全二叉树，通常用连续数组存储（父节点i的子节点为2i+1和2i+2），直接按索引遍历即可，完全不需要堆操作，也不会修改输入。用哈希表（如果元素范围有限，也可以用数组）统计每个元素的出现次数。
• 遍历第二个堆的所有元素，在哈希表中对应元素的计数减1；如果遇到哈希表中没有的元素，直接判定两个堆不相等。
• 最后检查哈希表中所有元素的计数是否都为0，若是则元素集合完全相等，否则不相等。

这个方法的时间复杂度是线性的，因为两次遍历都是O(n)，哈希表的插入、查询、更新操作平均都是O(1)时间。

场景2：判断两个堆的结构和元素完全一致（每个对应位置的元素都相同） #

这种情况同样可以在O(n)时间内完成：

• 如果堆是数组存储的，直接按顺序遍历两个数组，逐个比较对应索引的元素是否相同即可。
• 如果是链式存储的完全二叉树，按层次遍历的顺序逐个访问节点并比较元素，全程也是线性时间。

为什么会有人想到O(n log n)的解法？ #

不少人第一反应会考虑“复制两个堆，然后不断弹出堆顶元素比较”——但这种方法完全没必要：复制堆本身是O(n)时间，每次弹出堆顶又要O(log n)，n次下来就是O(n log n)。但我们根本不需要利用堆的优先级特性，直接遍历元素就足够了。

关于下界的说明 #

对于这两种场景，O(n)都是最优下界：因为最坏情况下，两个堆只有最后一个元素不同，我们必须遍历所有元素才能发现差异，不可能有比线性时间更优的解法。

内容的提问来源于stack exchange，提问作者U2EF1