Binary Heap Sort Algorithm in JavaScript

Use Case:

This post is a continuation of my previous post on building a binary max heap in JavaScript. Heap sort is an efficient sorting algorithm - O(n log n) - (both for timing and storage) that compares values against each other. Below is my concise implementation of this algorithm.

These functions are assumed to be placed inside of the Heap class we created in the previous post.

1. buildHeap Function

We need to create a way for an array data structure to be turned into a heap structure.

buildHeap = (array) => {
	this.maxSize += array.length
	for (let index of array) {
		heap.insert(index)
	}
	return heap.H
}

Our buildHeap function will accept an array structure, increase the maximum size allowed for our heap to fit the number of elements in our array, and then insert each value into our heap. This assumes that you've already created an instance of the Heap class. Then, it'll return the updated heap data.

2. heapSort Function

heapSort = () => { // O(n log n)
	var sorted = []
	for (var i = this.H.length - 1; i >= 0; i--) {
		sorted[i] = this.extractMax()
	}
	return sorted
}

Once we've constructed our binary heap (as outlined in the previous post), we simply need to create a loop that will run for the size of the heap and return our maximum values.

Here, we're adding them to our sorted array in backwards order so that our smallest values end up being first.

3. partialSort Function

partialSort = (k) => { // O(k log n)
	var results = []
	for (var i = k - 1; i >= 0; i--) {
		results[i] = this.extractMax()
	}
	return results
}

As an aside, let's say that you wanted to sort only a portion of the heap data set. Here, we've created a function called partialSort that accepts an integer of k that determines how large of a returned result set we'd like to receive.

This particular function can be done more quickly than the full heapSort function as it is only running on k elements instead of all elements - n.

4. Results

var array = [5,2,3,8,1,6,7,3,4,9]

var heap = new Heap(5)
heap.buildHeap(array)
console.log(heap.heapSort()) // 1,2,3,3,4,5,6,7,8,9
console.log(heap.partialSort(4)) // 6,7,8,9

Here we're creating and then building our heap and then logging the results of the 2 algorithms (note, that you can't call them back-to-back since the sorting algorithms remove elements when sorting). The run time of our heapSort algorithm, in this instance, was O(10 log 10) and the run time of our partialSort algorithm was O(4 log 10).