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

Gary Willoughby via Digitalmars-d-learn digitalmars-d-learn at
Mon Dec 28 11:29:25 PST 2015

On Monday, 28 December 2015 at 14:05:42 UTC, Ivan Kazmenko wrote:
> 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.

That's perhaps too much of a performance hit.

> 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.

That's actually a good idea. Sort it first, and it should still 
be balanced and correct. Then iteration is easy!

> 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.

I'll have to test parallel iteration.

More information about the Digitalmars-d-learn mailing list