digitalmars.D.learn - Whats wrong with binery heap or i am not understand something?
- AlexM (20/20) Apr 02 2020 Please explain me whats wrong with binery heap?!!!
- Dennis (13/14) Apr 02 2020 This has nothing to do with binaryheap and all to do with writeln.
- Dennis (3/5) Apr 02 2020 Correction: this only applies to `h`, the array slice `b` will
- WebFreak001 (16/36) Apr 02 2020 by iterating over it (writeln doing it) you are taking out all
- Steven Schveighoffer (5/8) Apr 02 2020 A binary heap has to move elements in order to iterate. So a save call
- Steven Schveighoffer (10/34) Apr 02 2020 writeln(h) actually removes all the elements from the heap to print it.
- AlexM (2/22) Apr 02 2020 Thank you very much for all responders!
Please explain me whats wrong with binery heap?!!! Simple example: import std.container.binaryheap; import std.stdio; void main() { int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; int[] b = new int[a.length]; auto h = BinaryHeap!(int[], "a > b")(b, 0); foreach (e; a) { h.insert(e); } writeln(b); // [1, 2, 3, 4, 7, 9, 10, 14, 8, 16] writeln(h); // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16] writeln(h.length); // 0 ??????? h.insert(21); writeln(h); // [21] ???????? writeln(h.length); // 0 ??????? }
Apr 02 2020
On Thursday, 2 April 2020 at 12:59:06 UTC, AlexM wrote:Please explain me whats wrong with binery heap?!!!This has nothing to do with binaryheap and all to do with writeln. writeln recognizes b and h as ranges, and prints them by iterating over each element, which advances the range to the end. You can see that the following actually prints what you expect: ``` writeln(b[]); // [1, 2, 3, 4, 7, 9, 10, 14, 8, 16] writeln(h.dup); // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16] writeln(h.length); // 10 h.insert(21); writeln(h.dup); // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16, 21] writeln(h.length); // 11 ```
Apr 02 2020
On Thursday, 2 April 2020 at 13:23:29 UTC, Dennis wrote:writeln recognizes b and h as ranges, and prints them by iterating over each element,Correction: this only applies to `h`, the array slice `b` will not be mutated by writeln.
Apr 02 2020
On Thursday, 2 April 2020 at 12:59:06 UTC, AlexM wrote:Please explain me whats wrong with binery heap?!!! Simple example: import std.container.binaryheap; import std.stdio; void main() { int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; int[] b = new int[a.length]; auto h = BinaryHeap!(int[], "a > b")(b, 0); foreach (e; a) { h.insert(e); } writeln(b); // [1, 2, 3, 4, 7, 9, 10, 14, 8, 16] writeln(h); // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16] writeln(h.length); // 0 ??????? h.insert(21); writeln(h); // [21] ???????? writeln(h.length); // 0 ??????? }by iterating over it (writeln doing it) you are taking out all elements from the binary heap. You will either need to .dup it (will cause memory allocation, will only make a single additional copy) or convert it to an array using .array (will cause memory allocation, you can use it multiple times but not use it as binary heap anymore) If BinaryHeap implemented a save() method it would be possible to do this without duplicating because writeln would call save to not modify the existing data. If you only want to get the length and do something with the data exactly once, you can call .length before using the data to get the length of the data. If you get length after iterating over your data, your data will be gone at this point. Otherwise you might want to try some containers library from dub for more advanced containers.
Apr 02 2020
On 4/2/20 9:25 AM, WebFreak001 wrote:If BinaryHeap implemented a save() method it would be possible to do this without duplicating because writeln would call save to not modify the existing data.A binary heap has to move elements in order to iterate. So a save call would be equivalent to a dup call. I think that's why it supports dup and not save. -Steve
Apr 02 2020
On 4/2/20 8:59 AM, AlexM wrote:Please explain me whats wrong with binery heap?!!! Simple example: import std.container.binaryheap; import std.stdio; void main() { int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; int[] b = new int[a.length]; auto h = BinaryHeap!(int[], "a > b")(b, 0); foreach (e; a) { h.insert(e); } writeln(b); // [1, 2, 3, 4, 7, 9, 10, 14, 8, 16] writeln(h); // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16] writeln(h.length); // 0 ??????? h.insert(21); writeln(h); // [21] ???????? writeln(h.length); // 0 ??????? }writeln(h) actually removes all the elements from the heap to print it. It's also ref-counted, and is not a forward range (no save is provided), so you have to dup it to print it: writeln(h.dup); So why would you need to do this? Because heaps have to mutate to iterate. Just printing it needs to move elements around, destroying the original heap in the process. Another case of why non-forward ranges shouldn't support copying. -Steve
Apr 02 2020
On Thursday, 2 April 2020 at 12:59:06 UTC, AlexM wrote:Please explain me whats wrong with binery heap?!!! Simple example: import std.container.binaryheap; import std.stdio; void main() { int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; int[] b = new int[a.length]; auto h = BinaryHeap!(int[], "a > b")(b, 0); foreach (e; a) { h.insert(e); } writeln(b); // [1, 2, 3, 4, 7, 9, 10, 14, 8, 16] writeln(h); // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16] writeln(h.length); // 0 ??????? h.insert(21); writeln(h); // [21] ???????? writeln(h.length); // 0 ??????? }Thank you very much for all responders!
Apr 02 2020