Heap Sort

Algorithm Steps

Build a max heap from the input array.
The largest element is now at the root of the heap.
Swap the root with the last element, then reduce the heap size by one.
Heapify the root to maintain the heap property.
Repeat steps 3 and 4 until the heap size is 1.

Heap Sort Program Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr

if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    heap_sort(arr)
    print("Sorted array is:", arr)