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.

>>     def sift_down(  )
>>
> ...
>
>>             c += 1 if c + 1 < @heap.size and @heap[c + 1] < @heap[c]
>>
>
> You probably wanted to say:
>             c += 1 if c + 1 < @heap.size and @comp[@heap[c + 1],  
> @heap[c]] < 0

Right you are.  Thanks!

James Edward Gray II