Implement an iterator on a binary heap

Question

I am looking for a way to implement an iterator on binary heaps (maximum or minimum).

That is, by using it’s nextNode() function for the i-th time, can get the i-th (greater or smaller) element in the heap.

Note that this operation happens without actually extracting the heap’s root!

My initial thoughts were:

• Actually extract i elements, push them into a stack, and then insert them back into the heap after getting the i-th value. This takes O(i*log(n)) for each function call.
• Keep an auxiliary sorted data structure, which can allow to lookup the next value in O(1), however updates would take O(n).

I understand these approaches eliminate the benefits of using heaps, so I’m looking for a better approach.

Goiter

I think this is the same question as #7651417 - you don't have to spend O(i) for operations on the sorted auxiliary structure. – Gary

Do you need your iterator to remain valid when the heap changes? – Hun

@Hun No, not necessarily. – Goiter

Answer 1

It's not clear what the use-case for this is, so it's hard to say what would make a solution viable, or better than any other solution.

That said, I suggest a small alteration to the general "extract and sort" ideas already thrown around: If we're fine making changes to the data structure, we can do our sorting in place.

The basic implementation suggested on Wikipedia is a partially sorted list under-the-hood. We can pay a (hopefully) one-time O(n log(n)) cost to sort our heap when the first time next() is called, after which next is O(1). Critically, a fully-sorted list is still a valid heap.

Furthermore, if you consider the heapsort algorithm, you can start at stage two, because you're starting with a valid heap.

Trilateral