Is it possible to elegantly create a range over a binary heap?

[Ivan Kazmenko via Digitalmars-d-learn]

On Monday, 28 December 2015 at 12:58:36 UTC, Gary Willoughby 
wrote:
> On Sunday, 27 December 2015 at 22:42:21 UTC, Ivan Kazmenko 
> wrote:
>> Or do you mean you want to print variables in order without 
>> modifying the array?  Sounds like this would require at least 
>> N log N time and N additional memory for an N-element heap 
>> anyway (or quadratic time and constant memory).  So, you can 
>> just copy the array and exhaust the copied binary heap, 
>> getting the same asymptotic complexity: N log N time and N 
>> additional memory.
>>
> Thanks. I wanted to iterate through the range without modifying 
> the original array but like you said the only way to do that is 
> by copying the data which is not ideal.

Hmm.  On second thought:

1. You can find maximum, then second maximum, then third maximum 
and so on - each in constant memory and linear time.  So, if 
performance is somehow not an issue, there is a way to do it 
@nogc but in N^2 operations.

2. If you output the whole array anyway, you may sort the array 
in place.  A sorted array obeys the heap property, so subsequent 
heap operations will still work.

3. The tricky part is when we want to support parallel iteration 
over the same heap.  If we look closely at one iteration of 
heapsort algorithm, it will perhaps become clear how to output 
values so that the array is a heap between any two consecutive 
output operations.  At the very least, our heap struct over the 
array can just track which part of the array is already sorted, 
and work with it separately.

4. Reading and modifying the heap in parallel at the same time 
does not look possible anyway, so this is as far as we can get.

Ivan Kazmenko.