www.digitalmars.com         C & C++   DMDScript  

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

reply Gary Willoughby <dev nomad.so> writes:
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
parent reply Gary Willoughby <dev nomad.so> writes:
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
parent reply 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
parent reply Gary Willoughby <dev nomad.so> writes:
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
parent reply 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 
 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.
Dec 28 2015
parent Gary Willoughby <dev nomad.so> writes:
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