Andrei Alexandrescu Wrote: > Bill Baxter wrote: > > On Fri, Jan 30, 2009 at 11:49 AM, Andrei Alexandrescu > > <[email protected]> wrote: > >> A "computer science heap" is a structure that offers fast access to the > >> largest element and fast extraction of it (which in turn provides access to > >> the next largest element etc.). > > > > In response to your previous question of how to distinguish from a > > memory heap, you can use the specific name for the kind of heap it is, > > like BinaryHeap, Binomial Heap, Fibbonocci Heap, etc. > > BinaryHeap it is. Thanks! > > >> I'm just done working on the heap in std.algorithm. Now, it turns out that > >> heap supports both a meaningful definition as a full-fledged container, and > >> a beautiful definition as a range. > >> > >> If Heap is a range, you initiate it with another range, which Heap > >> organizes > >> in the heap manner. Then, successive calls to next() nicely extract > >> elements > >> starting from the largest. If the underlying range supports put(), then > >> Heap > >> also supports put() to insert into the heap. > >> > >> Heap as a container would offer similar primitives but in addition would > >> "own" its data (would call destructors upon destruction, and would support > >> value copying). > >> > >> What do you think? Should I make Heap a container or a range? > > > > Both sound useful depending on circumstances. One provides the > > all-in-one convenient solution, the other is more of a "non-invasive > > heap". > > > > If you emphasize the non-invasive version, then creating the > > all-in-one version out of that should be pretty easy. But you can't > > take an all-in-one and turn it non-invasive so easily. > > Ah, never mind all that. I realized that I can't have a heap range. This > is because heaps must mutate the underlying range in-place and any copy > will mess the heap up. Here's the example that clarify it for me: > > int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; > auto h = Heap!(int[])(a); > assert(equal(take(5, h) == [ 8, 9, 10, 14, 16 ]); > > At this point the mutations done by take messed up h already!!
I would have expected index take(h,5)[0] to be 16... I still have yet to come to terms with passing ranges by value. I would expect take to modify my range. I naturally expect heaps to be destructive as elements are taken out. I also expect ranges to shrink. I don't see any issue...
