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
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: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 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.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
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 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
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: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.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.
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