Heap Sort

Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to the selection sort where we first find the minimum element and place the minimum element at the beginning. Repeat the same process for the remaining elements.

def heap_sort(arr):
	# Build a heap from the input array
	build_heap(arr)
 
	# Repeat until the heap contains only one element
	for i in range(len(arr) - 1, 0, -1):
		# Swap the root element with the last element
		arr[0], arr[i] = arr[i], arr[0]
 
		# Remove the last element (which is now in the correct position)
		heap_size = i
		heapify(arr, 0, heap_size)
 
	# Reverse the order of the elements to obtain the sorted array
	arr.reverse()
 
def build_heap(arr):
	# Build a max heap from the input array
	n = len(arr)
	for i in range(n // 2 - 1, -1, -1):
		heapify(arr, i, n)
 
def heapify(arr, i, heap_size):
	# Heapify the subtree rooted at i in the input array
	largest = i
	left = 2 * i + 1
	right = 2 * i + 2
 
	if left < heap_size and arr[left] > arr[largest]:
		largest = left
 
	if right < heap_size and arr[right] > arr[largest]:
		largest = right
 
	if largest != i:
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, largest, heap_size)
 
# Example usage
arr = [5, 2, 9, 1, 5, 6]
heap_sort(arr)
print(arr)
 

Javascript

function heapify(arr, i, heapSize) {
    const resultArr = [...arr]; // Create a new array to hold the result
 
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
 
    if (left < heapSize && resultArr[left] > resultArr[largest]) {
        largest = left;
    }
 
    if (right < heapSize && resultArr[right] > resultArr[largest]) {
        largest = right;
    }
 
    if (largest !== i) {
        [resultArr[i], resultArr[largest]] = [resultArr[largest], resultArr[i]];
        // Recursive call with the updated array
        return heapify(resultArr, largest, heapSize);
    }
 
    return resultArr; // Return the result array
}
 
const inputArr = [4, 10, 3, 5, 1]; 
const i = 0; 
const heapSize = inputArr.length; 
const resultArr = heapify(inputArr, i, heapSize); 
console.log("Original Array:", inputArr); 
console.log("Heapified Array:", resultArr);
dv.paragraph("input →" + inputArr);
dv.paragraph("result →" + resultArr);