8

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.

BlueSun
  • 3,541
  • 1
  • 18
  • 37
Ahmed Hammad
  • 2,798
  • 4
  • 18
  • 35
  • 2
    I think this is the same question as https://stackoverflow.com/questions/7650917/oklogk-time-algorithm-to-find-kth-smallest-element-from-a-binary-heap - you don't have to spend O(i) for operations on the sorted auxiliary structure. – Nickolay May 15 '19 at 00:09
  • Do you need your iterator to remain valid when the heap changes? – Jeff May 20 '19 at 18:12
  • @Jeff No, not necessarily. – Ahmed Hammad May 20 '19 at 18:22

1 Answers1

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.

ShapeOfMatter
  • 991
  • 6
  • 25