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.
