Andrei Alexandrescu wrote:
> 
> 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!!

Hm... so assuming this is a min heap, I have:

a = [4,1,3,2,16,9,10,14,8,7];
h = [1,2,3,4,7,9,10,14,8,16];
take(5, h);
h = [8,10,9,16,14];

Shouldn't take call next repeatedly on the heap, which will in turn perform a popHeap operation?  It's difficult to be sure what the result will be after take(5,h) occurs, but it should still be a valid heap, correct?


Sean

Sean Kelly wrote:
> Andrei Alexandrescu wrote:
>>
>> 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!!
> 
> Hm... so assuming this is a min heap, I have:
> 
> a = [4,1,3,2,16,9,10,14,8,7];
> h = [1,2,3,4,7,9,10,14,8,16];
> take(5, h);
> h = [8,10,9,16,14];
> 
> Shouldn't take call next repeatedly on the heap, which will in turn perform a popHeap operation?  It's difficult to be sure what the result will be after take(5,h) occurs, but it should still be a valid heap, correct?

Oh, I would also expect:

a = [8,10,9,16,14, garbage];

Since it isn't aware of the length adjustment.  Perhaps this is what you meant?


Sean

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

I'm not seeing that. take should iterate through _h_, which will pop elements from _a_ (or a copy thereof) while maintaining the heap invariant.

Sean Kelly wrote:
> Sean Kelly wrote:
>> Andrei Alexandrescu wrote:
>>>
>>> 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!!
>>
>> Hm... so assuming this is a min heap, I have:
>>
>> a = [4,1,3,2,16,9,10,14,8,7];
>> h = [1,2,3,4,7,9,10,14,8,16];
>> take(5, h);
>> h = [8,10,9,16,14];
>>
>> Shouldn't take call next repeatedly on the heap, which will in turn perform a popHeap operation?  It's difficult to be sure what the result will be after take(5,h) occurs, but it should still be a valid heap, correct?
> 
> Oh, I would also expect:
> 
> a = [8,10,9,16,14, garbage];
> 
> Since it isn't aware of the length adjustment.  Perhaps this is what you meant?
> 
> 
> Sean

Yah, that's what I meant. h still thinks its length is 10 and that those 10 elements respect the heap property.

Andrei

Andrei Alexandrescu wrote:
> Sean Kelly wrote:
>> Sean Kelly wrote:
>>> Andrei Alexandrescu wrote:
>>>>
>>>> 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!!
>>>
>>> Hm... so assuming this is a min heap, I have:
>>>
>>> a = [4,1,3,2,16,9,10,14,8,7];
>>> h = [1,2,3,4,7,9,10,14,8,16];
>>> take(5, h);
>>> h = [8,10,9,16,14];
>>>
>>> Shouldn't take call next repeatedly on the heap, which will in turn perform a popHeap operation?  It's difficult to be sure what the result will be after take(5,h) occurs, but it should still be a valid heap, correct?
>>
>> Oh, I would also expect:
>>
>> a = [8,10,9,16,14, garbage];
>>
>> Since it isn't aware of the length adjustment.  Perhaps this is what you meant?
>>
>>
>> Sean
> 
> Yah, that's what I meant. h still thinks its length is 10 and that those 10 elements respect the heap property.
> 
> Andrei

Since take is a mutator, that implies that h needs to be a reference type or a by ref value, right?  So, why not make it so?

Later,
Brad

I don't know if it matters, but I added the heap routines to Tango because I wanted heapsort, so they kind of came for free.  Perhaps a key distinction between ranges and algorithms is that algorithms may mutate the underlying data, but ranges may not?  I've been trying to think of another example of a mutating range and I haven't come up with one yet... unless you consider input ranges mutating, I suppose.


Sean

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

regarding your previous question:
isn't a Heap also called a Priority Queue?

On Fri, Jan 30, 2009 at 4:01 PM, Yigal Chripun <yigal100@gmail.com> wrote:
>
> regarding your previous question:
> isn't a Heap also called a Priority Queue?
>

I the distinction is that a Heap is one way to implement a Priority Queue.  You could implement a priority queue by scanning a linked list for the smallest item and it would still be a (really inefficient) Priority Queue.

--bb

Bill Baxter wrote:
> On Fri, Jan 30, 2009 at 4:01 PM, Yigal Chripun<yigal100@gmail.com>  wrote:
>> regarding your previous question:
>> isn't a Heap also called a Priority Queue?
>>
>
> I the distinction is that a Heap is one way to implement a Priority
> Queue.  You could implement a priority queue by scanning a linked list
> for the smallest item and it would still be a (really inefficient)
> Priority Queue.
>
> --bb

Ah. right.. :)

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 think this depends on whether heap operations are required (and usable) in places other than in a heap container.

For some applications (certain graph algorithms), you want two ways to access the data. You use an IndexedPriorityQueue structure, which contains both a heap of (key, value) pairs ordered by value, allowing you to pop the item with minimum value in O(log n) time, and also an array allowing you to access any item by key in O(1) time. Whenever you move items in the heap, you update the array at the same time.
It's impossible to implement such a data stucture using STL heap primitives, and likewise, my guess is that it would be impossible in both a range and container Heaps (basically, you need to be able to hook in a user-defined function to be called whenever items are swapped in the heap).
But if it is possible in one but not the other implementation, it should be favoured.