2010/9/30 Levente Uzonyi <leves at elte.hu>:
> On Thu, 30 Sep 2010, Nicolas Cellier wrote:
>
>> Hi,
>> I just saw this:
>>
>> Heap>>privateRemoveAt: index
>>        "Remove the element at the given index and make sure the sorting
>> order is okay"
>>        | removed |
>>        removed := array at: index.
>>        array at: index put: (array at: tally).
>>        array at: tally put: nil.
>>        tally := tally - 1.
>>        index > tally ifFalse:[
>>                "Use #downHeapSingle: since only one element has been
>> removed"
>>                self downHeapSingle: index].
>>        ^removed
>>
>> This means that an element removal triggers a new sort phase... (even
>> a simplified one costs)
>
> This method just restores the heap invariant, it doesn't sort the heap. It
> has O(log(n)) time complexity.
>
>> I think this could be more efficient:
>>
>> Heap>>privateRemoveAt: index
>>        "Remove the element at the given index and make sure the sorting
>> order is okay"
>>        | removed |
>>        removed := array at: index.
>>        tally := tally - 1.
>>        array replaceFrom: index to: tally with: array startingAt: index +
>> 1.
>>        array at: tally + 1 put: nil.
>>        indexUpdateBlock ifNotNil: [
>>                index to: tally do: [:i | self updateObjectIndex: i]].
>>        ^removed
>>
>> Did I miss a good reason justifying to re-sort ?
>
> The method comment is a bit misleading because the method doesn't really
> sort the heap.
>
>
> Levente
>

Ah yes, of course, my mistake... It's equivalent to a tree.
I was blinded by the assumption that #do: would enumerate in sort
order, which it does not (but we don't care, we won't enumerate past
the #first).
Hmm gonna have a class comment to document...

Nicolas

>>
>> Nicolas
>>
>>
>
>