Heap Sort

Heap Sort :

Author(s) : J. W. J. Williams Date : 1964

Heap sort is a sorting algorithm that utilizes a heap data structure for efficient element arrangement. It follows a divide-and-conquer approach, initially building a max-heap (where the root has the largest value) from the input array. This process involves repeatedly swapping elements to ensure the heap property holds (parent element greater than or equal to children). Once the max-heap is constructed, the largest element (root) is extracted and placed at the end of the sorted array. The heap is then rearranged by swapping the root with the last element and restoring the heap property. This process of extraction, rearrangement, and swapping continues until the entire array is sorted in descending order. For ascending order, a min-heap (root has the smallest value) would be used.

Time Complexity O(n log n)
Best Case O(n log n)
Worst Case O(n log n)
Space Complexity O(1)
Stable No

Code Integration:

* the code might contain some bugs or may not work correctly

Python JavaScript Java Go C
def heapify(arr, n, i):
	largest = i  # Initialize largest as root
	lf = 2 * i + 1  # left = 2*i + 1
	right = 2 * i + 2  # right = 2*i + 2

	# See if left child is larger than root
	if lf < n and arr[i] < arr[lf]:
		largest = lf

	# See if right child is larger
	if right < n and arr[largest] < arr[right]:
		largest = right

	# Swap if largest is not root
	if largest != i:
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest)

def heap_sort(arr):
	n = len(arr)

	# Build a maxheap.
	for i in range(n // 2 - 1, -1, -1):
		heapify(arr, n, i)

	# One by one extract an element from heap
	for i in range(n - 1, 0, -1):
		arr[i], arr[0] = arr[0], arr[i]  # swap
		heapify(arr, i, 0)  # reduce heap size and maintain heap property

# Test array
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print('Sorted array is:', arr)
function heapify(arr, n, i) {
	let largest = i;  // Initialize largest as root
	let left = 2 * i + 1;  // left = 2*i + 1
	let right = 2 * i + 2;  // right = 2*i + 2

	// See if left child is larger than root
	if (left < n && arr[i] < arr[left]) {
		largest = left;
	}

	// See if right child is larger
	if (right < n && arr[largest] < arr[right]) {
		largest = right;
	}

	// Swap if largest is not root
	if (largest !== i) {
		let temp = arr[i];
		arr[i] = arr[largest];
		arr[largest] = temp;
		heapify(arr, n, largest);
	}
}

function heapSort(arr) {
	let n = arr.length;

	// Build a maxheap.
	for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
		heapify(arr, n, i);
	}

	// One by one extract an element from heap
	for (let i = n - 1; i > 0; i--) {
		// Move current root to end
		let temp = arr[0];
		arr[0] = arr[i];
		arr[i] = temp;
		heapify(arr, i, 0);
	}
}

// Test array
let arr = [12, 11, 13, 5, 6, 7];
heapSort(arr);
console.log('Sorted array is:', arr);
public class HeapSort {
	public static void heapify(int arr[], int n, int i) {
		int largest = i; // Initialize largest as root
		int left = 2 * i + 1; // left = 2*i + 1
		int right = 2 * i + 2; // right = 2*i + 2

		// See if left child is larger than root
		if (left < n && arr[i] < arr[left]) {
			largest = left;
		}

		// See if right child is larger
		if (right < n && arr[largest] < arr[right]) {
			largest = right;
		}

		// Swap if largest is not root
		if (largest != i) {
			int temp = arr[i];
			arr[i] = arr[largest];
			arr[largest] = temp;
			heapify(arr, n, largest);
		}
	}

	public static void heapSort(int arr[]) {
		int n = arr.length;

		// Build a maxheap.
		for (int i = n / 2 - 1; i >= 0; i--) {
			heapify(arr, n, i);
		}

		// One by one extract an element from heap
		for (int i = n - 1; i > 0; i--) {
			// Move current root to end
			int temp = arr[0];
			arr[0] = arr[i];
			arr[i] = temp;
			heapify(arr, i, 0);
		}
	}

	public static void main(String args[]) {
		int arr[] = {12, 11, 13, 5, 6, 7};
		heapSort(arr);

		System.out.println("Sorted array is: ");
		for (int i = 0; i < arr.length; ++i) {
			System.out.print(arr[i] + " ");
		}
	}
}
package main

import (
	"fmt"
)

func heapify(arr []int, n int, i int) {
	largest := i  // Initialize largest as root
	left := 2*i + 1  // left = 2*i + 1
	right := 2*i + 2 // right = 2*i + 2

	// See if left child is larger than root
	if left < n && arr[i] < arr[left] {
		largest = left
	}

	// See if right child is larger
	if right < n && arr[largest] < arr[right] {
		largest = right
	}

	// Swap if largest is not root
	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest)
	}
}

func heapSort(arr []int) {
	n := len(arr)

	// Build a maxheap.
	for i := n/2 - 1; i >= 0; i-- {
		heapify(arr, n, i)
	}

	// One by one extract an element from heap
	for i := n - 1; i > 0; i-- {
		// Move current root to end
		arr[0], arr[i] = arr[i], arr[0]
		heapify(arr, i, 0)
	}
}

func main() {
	arr := []int{12, 11, 13, 5, 6, 7}
	heapSort(arr)

	fmt.Println("Sorted array is: ", arr)
}
#include <stdio.h>

void swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void heapify(int arr[], int n, int i) {
	int largest = i; // Initialize largest as root
	int left = 2 * i + 1; // left = 2*i + 1
	int right = 2 * i + 2; // right = 2*i + 2

	// See if left child is larger than root
	if (left < n && arr[i] < arr[left]) {
		largest = left;
	}

	// See if right child is larger
	if (right < n && arr[largest] < arr[right]) {
		largest = right;
	}

	// Swap if largest is not root
	if (largest != i) {
		swap(&arr[i], &arr[largest]);
		heapify(arr, n, largest);
	}
}

void heapSort(int arr[], int n) {
	// Build a maxheap.
	for (int i = n / 2 - 1; i >= 0; i--) {
		heapify(arr, n, i);
	}

	// One by one extract an element from heap
	for (int i = n - 1; i > 0; i--) {
		// Move current root to end
		swap(&arr[0], &arr[i]);
		heapify(arr, i, 0);
	}
}

int main() {
	int arr[] = {12, 11, 13, 5, 6, 7};
	int n = sizeof(arr) / sizeof(arr[0]);
	heapSort(arr, n);
	printf("Sorted array is: ");
	for (int i = 0; i < n; ++i) {
		printf("%d ", arr[i]);
	};

	return 0;
}
light dark