Is it possible to elegantly create a range over a binary heap?
Gary Willoughby via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
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