On Tue, 26 Jul 2005 19:12:47 +0200, James Edward Gray II  
<james / grayproductions.net> wrote:

> On Jul 26, 2005, at 9:41 AM, Dominik Bathon wrote:
>
>>> In fact, here's a basic pure Ruby implementation (not exhaustively
>>> tested) using the system I just described:
>>>
>>
>> I found two problems ;-)
>
> Good thing someone is watching over me!
>
>>> class Heap
>>>
>> ...
>>
>>>     def extract(  )
>>>         extracted = @heap[1]
>>>         @heap[1] = @heap.pop unless @heap.size.zero?
>>>         sift_down
>>>         extracted
>>>     end
>>>
>>
>> This doesn't really extract the last element...
>
> Can you please show a failing example?  I tried to find one and couldn't.

Maybe I havn't been clear enough, I meant the heap can't get empty, you  
can't remove the last remaining element:

>> h = Heap.new(1,2)
=> [1, 2]
>> h.extract
=> 1
>> h
=> [2]
>> h.extract
=> 2
>> h
=> [2] # <= the 2 is still in there
>> h.extract
=> 2
>> h.extract
=> 2

and so on. The problem is:

>> a=[nil, 1]
=> [nil, 1]
>> a[1] = a.pop
=> 1
>> a
=> [nil, 1]

Dominik