What are the best known bounds for comparing two binary heaps for equality?

Question

In particular without modifying the input.

I've so far been unable to find anything on this, I wonder if it has a solution better than the obvious O(n log n) time.

Answer 1

According to your definition, two heaps are equal if they yield the same sequence of elements when extracting their maximum element repeatedly. Since that amounts to destructively sorting the elements in the heap, equality is also equivalent to saying that the two sequences of heap elements when sorted are equal. But that is equivalent to multiset equality between the two heaps.

Checking multiset equality can be done in O(n) (amortized), e.g. by using a hash table to map each element of the first heap to its frequency, which can be done non-destructively in O(n), and then checking the elements of the second heap against the hash table, which can also be done in O(n).

Since it is not possible to check equality without considering each element at least once, O(n) is also the tightest bound on checking equality of two binary heaps.