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