Heap Sort - Algorithm, Visualization, Examples

Contents

AlgorithmCode

Algorithm Steps❯

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

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
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)