Why do Heap re-sort when it removes elements ?

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

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

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