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

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?


Andrei

Andrei Alexandrescu 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.).
> 
> 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?
> 
> 
> Andrei

I suppose it comes down to whether or not the typical case is to either have a heap or heap-view of another container.  I'd suspect the first, to be honest.

You could always just have Heap and HeapView.  :)

  -- Daniel

On Fri, Jan 30, 2009 at 11:49 AM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> 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.


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

--bb

Bill Baxter wrote:
> On Fri, Jan 30, 2009 at 11:49 AM, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> 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!!


Andrei

Hello Andrei,

> What do you think? Should I make Heap a container or a range?
> 
> Andrei
> 

what would be the problem of making it (optionaly) both? 

On Fri, Jan 30, 2009 at 12:14 PM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Bill Baxter wrote:
>>
>> On Fri, Jan 30, 2009 at 11:49 AM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> 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!!

Messed 'h' up or messed 'a' up?

Anyway, in that case it would be nice if you can easily run the heap indirectly on an index or pointer buffer.

Will something like this work?
HeavyElement[] arrayOfHeavies;
auto h = Heap!(int[], (int i, int j){return
arrayOfHeavies[i]<arrayOfHeavies[j];} )( 0..arrayOfHeavies.length )

Now   arrayOfHeavies[h.pop()] should give you the smallest element of the array of heavies, without ever having to copy/swap anything but ints.

--bb

Andrei Alexandrescu Wrote:

> Bill Baxter wrote:
> > On Fri, Jan 30, 2009 at 11:49 AM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> 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...

Bill Baxter wrote:
> On Fri, Jan 30, 2009 at 12:14 PM, Andrei Alexandrescu
>> 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!!
> 
> Messed 'h' up or messed 'a' up?

'a' is messed up (mutated) by definition. The problem is that after h was copied to do take's deed, it got messed up (i.e., doesn't respect the heap property anymore).

> Anyway, in that case it would be nice if you can easily run the heap
> indirectly on an index or pointer buffer.
> 
> Will something like this work?
> HeavyElement[] arrayOfHeavies;
> auto h = Heap!(int[], (int i, int j){return
> arrayOfHeavies[i]<arrayOfHeavies[j];} )( 0..arrayOfHeavies.length )
> 
> Now   arrayOfHeavies[h.pop()] should give you the smallest element of
> the array of heavies, without ever having to copy/swap anything but
> ints.

Yah, that should work. You just need to initially fill the heap with the numbers 0 to arrayOfHeavies.length. I presume that's what you meant with the illegal slicing notation :o).


Andrei

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

Both ways have advantages and disadvantages. My early experiments involved passing by reference and it was an absolute mess: I'd forget a "ref" here and there with weird results, or I'd forget to save a copy of my range and I'd find is shrunk like an dehydrated fig in no time. One advantage of pass by value is that code is shorter and nicer - no need for a lot of temporaries.

Andrei

On Fri, Jan 30, 2009 at 1:17 PM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Bill Baxter wrote:
>>
>> On Fri, Jan 30, 2009 at 12:14 PM, Andrei Alexandrescu
>>>
>>> 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!!
>>
>> Messed 'h' up or messed 'a' up?
>
> 'a' is messed up (mutated) by definition. The problem is that after h was
> copied to do take's deed, it got messed up (i.e., doesn't respect the heap
> property anymore).
>
>> Anyway, in that case it would be nice if you can easily run the heap indirectly on an index or pointer buffer.
>>
>> Will something like this work?
>> HeavyElement[] arrayOfHeavies;
>> auto h = Heap!(int[], (int i, int j){return
>> arrayOfHeavies[i]<arrayOfHeavies[j];} )( 0..arrayOfHeavies.length )
>>
>> Now   arrayOfHeavies[h.pop()] should give you the smallest element of the array of heavies, without ever having to copy/swap anything but ints.
>
> Yah, that should work. You just need to initially fill the heap with the numbers 0 to arrayOfHeavies.length. I presume that's what you meant with the illegal slicing notation :o).

Ok. great.  I thought that the slicing notation to make a sequence worked everywhere now in D2.  I guess it's only inside a foreach.

--bb