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.
