felipernb/algorithms.js — pull request #38 by lifebeyondfife (2014-06-02 11:43:25+00:00)
Title: Add Heap Sort algorithm (using existing Heap data structure implementation).

O(n.logn) sorting algorithm implementation that uses algorithm.js' existing heap data structure. The initial array of elements to be sorted is used to create a heap data structure by calling the heapify() method - an O(n) operation.

Removing the head of the heap by calling extract() yields the smallest element of the array, and implicitly recreates a valid heap structure by calling the _siftDown() member function - an O(logn) operation. This is done for each of the n-1 elements remaining in the heap, resulting in an O(n.logn) runtime.