I hope you all don’t mind me opening all these topics. Hopefully they can be useful in the next update.
In Chapter 32, Heapsort, you have the code line heap.siftDown(from: 0, upTo: index) and you give a comment:
To support heap sort, you’ve added the
upToparameter to thesiftDownmethod.
However, you don’t include the code in the chapter text to accomplish that as far as I could see. It would be helpful to include that implementation.
On a slightly different topic, your illustrations show an in-place sort. Your code also does an in-place sort, but the benefit of an in-place sort is that you use O(1) space. However, in your code example you make a copy of the Heap to preserve the original heap property. Doesn’t that mean the algorithm is O(n) space complexity now? And if it’s going to O(n) space, wouldn’t it be easier to call heap.remove() with a loop? Then you wouldn’t need to worry about sifting at all since that’s handled by the heap. Alternatively, you could write a heapsort function (that’s not an extension on Heap) that takes an array and does the sort completely in-place.