Heapsort inefficiencies

[RyanNaughton]

One of the key advantages of heap sort is it can be an in place algorithm (https://en.wikipedia.org/wiki/In-place_algorithm); however, your implementation does not do an in place implementation:

https://github.com/kanwei/algorithms/blob/master/lib/algorithms/sort.rb#L85-L90

Instead, you are popping the values off the heap and putting them in a new array (when they could be kept in that array but moved to the end). Instead of calculating the size of the array in the heap, you could keep an index for the end of the heap within the array, and thus move the sorted values that have been popped off to the end of the actual array and decrement the heap's index.

At a minimum, the array here could be instantiated with the known size of the container. That prevents the array from being resized repeatedly (Ruby resizes an array when it hits 3, 20, 37, 56, 85, ... sizes, see here: https://github.com/ruby/ruby/blob/ruby_2_0_0/array.c#L183)

[bcc32]

The Heap implementation has been replaced with a Fibonacci heap, rather than an array-based binary heap, at this point. I think, if the heapsort were ever to be implemented in-place, it'd have to be a separate heap implementation now.