Heap Sort Algorithm Implementation

This function implements the heap sort algorithm to sort an array.

Technology Stack : array, bisect, calendar, cmath, collections, contextlib, csv, datetime, functools, html, http.client, heapq, itertools, json, locale, math, multiprocessing, os, random, re, shutil, smtplib, statistics, subprocess, sys, threading, time, unittest, urllib.request

Code Type : Sort function

Code Difficulty : Intermediate

                
                    
import array
import bisect
import calendar
import cmath
import collections
import contextlib
import csv
import datetime
import functools
import html
import http.client
import heapq
import itertools
import json
import locale
import math
import multiprocessing
import os
import random
import re
import shutil
import smtplib
import statistics
import subprocess
import sys
import threading
import time
import unittest
import urllib.request

def max_heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        max_heapify(arr, n, largest)

def build_max_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        max_heapify(arr, n, i)

def heap_sort(arr):
    n = len(arr)
    build_max_heap(arr)
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        max_heapify(arr, i, 0)