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

>
> Nicolas
>
>