Google - Heapsort

by Anton Bagayev

JavaScript

function swap(array, idx1, idx2) {
	let temp = array[idx1];
	array[idx1] = array[idx2];
	array[idx2] = temp;
}

function buildMaxHeap(array) {
	// get the index of last element's parent
	let i = Math.floor((array.length - 1) / 2);
	
	// continue heapifying the array until the parent node is reached
	while (i >= 0) {
		heapify(array, i, array.length);
		i--;
	}
}

function heapify(array, curr, max) {
	let index, leftChild, rightChild;
	
	while (curr < max) {
		// get indexes of the children of the current element
		index = curr;
		leftChildIndex = 2 * index + 1;
		rightChildIndex = 2 * index + 2;
		
		// find the largest existing child element that is greater than current element
		if ((leftChildIndex < max) && (array[leftChildIndex] > array[index])) {
			index = leftChildIndex;
		}
		if ((rightChildIndex < max) && (array[rightChildIndex] > array[index])) {
			index = rightChildIndex;
		}
		
		// if we didn't find the larger child - return from current iteration
		// otherwise - swap parent with largest child and set the current index to index of that largest child
		if (index == curr) {
			return;
		} else {
			swap(array, curr, index);
			curr = index;
		}
	}
}

function heapsort(array) {
	buildMaxHeap(array);
	
	let lastElementIndex = array.length - 1;
	while (lastElementIndex > 0) {
		swap(array, 0, lastElementIndex);
		heapify(array, 0, lastElementIndex);
		lastElementIndex--;
	}
	
	return array;
}


console.log(heapsort([3, 19, 1, 14, 8, 7, 19]));