## digitalmars.D.learn - Is it possible to elegantly create a range over a binary heap?

• Gary Willoughby (8/8) Dec 27 2015 I have a binary tree storing ints implemented using an array. The
• Gary Willoughby (4/12) Dec 27 2015 Some explanatory reference:
• Ivan Kazmenko (13/28) Dec 27 2015 If you implement a struct with range primitives over it, you can
• Gary Willoughby (7/19) Dec 28 2015 Thanks. I wanted to iterate through the range without modifying
• Ivan Kazmenko (20/33) Dec 28 2015 Hmm. On second thought:
• Gary Willoughby (5/21) Dec 28 2015 That's actually a good idea. Sort it first, and it should still
```I have a binary tree storing ints implemented using an array. The
internal state looks like this:

8,7,6,4,1,3,5,2

When extracting this data, it is returned as 8,7,6,5,4,3,2,1.

Is it possible to elegantly add a range on top of the internal
state to return the correct value order I would expect when
extracting? Is there an algorithm documented somewhere for doing
this?
```
Dec 27 2015
```On Sunday, 27 December 2015 at 17:23:35 UTC, Gary Willoughby
wrote:
I have a binary tree storing ints implemented using an array.
The internal state looks like this:

8,7,6,4,1,3,5,2

When extracting this data, it is returned as 8,7,6,5,4,3,2,1.

Is it possible to elegantly add a range on top of the internal
state to return the correct value order I would expect when
extracting? Is there an algorithm documented somewhere for
doing this?

Some explanatory reference:

https://en.wikipedia.org/wiki/Binary_tree#Arrays
```
Dec 27 2015
Ivan Kazmenko <gassa mail.ru> writes:
```On Sunday, 27 December 2015 at 20:01:47 UTC, Gary Willoughby
wrote:
On Sunday, 27 December 2015 at 17:23:35 UTC, Gary Willoughby
wrote:
I have a binary tree storing ints implemented using an array.
The internal state looks like this:

8,7,6,4,1,3,5,2

When extracting this data, it is returned as 8,7,6,5,4,3,2,1.

Is it possible to elegantly add a range on top of the internal
state to return the correct value order I would expect when
extracting? Is there an algorithm documented somewhere for
doing this?

Some explanatory reference:

https://en.wikipedia.org/wiki/Binary_tree#Arrays

If you implement a struct with range primitives over it, you can
use it as a range.

See the second code example in std.container.binaryheap's docs at
http://dlang.org/phobos/std_container_binaryheap.html#.BinaryHeap.

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.

Ivan Kazmenko.
```
Dec 27 2015
```On Sunday, 27 December 2015 at 22:42:21 UTC, Ivan Kazmenko wrote:
If you implement a struct with range primitives over it, you
can use it as a range.

See the second code example in std.container.binaryheap's docs
at
http://dlang.org/phobos/std_container_binaryheap.html#.BinaryHeap.

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.

Ivan Kazmenko.

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.

std.container.binaryheap looks like it implements the range
interface and consumes the original during iteration. I'll
probably do that too.
```
Dec 28 2015
Ivan Kazmenko <gassa mail.ru> writes:
```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

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.
```
Dec 28 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.
```
Dec 28 2015