**Heap sort** is a sorting algorithm that takes the input data and sorts it in *ascending* or *descending* order. A **[Heap](https://www.educative.io/answers/what-is-a-heap)** is a tree-like structure which is built using the input data. 

The algorithm requires *3* steps to complete the sorting procedure:
1. Create a heap with the input data.

2. Sort the elements of the heap are sorted in ascending order. 

3. Swap the root node with the last node and delete the last node from the heap. 

Following slides will assist you in understanding this concept better:

# Code

The following codes implement the heap sort algorithm in C++ and Python.

#include <iostream> 
using namespace std; 
  
// To heapify a subtree rooted with node i which is 
// an index in arr[]. n is size of heap 
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // set largest as root 
    int l = 2 * i + 1; // left = 2*i + 1 
    int r = 2 * i + 2; // right = 2*i + 2 
  
    // If left child is larger than root 
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 
  
    // If right child is larger than largest so far 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 
  
    // If largest is not root 
    if (largest != i) { 
        swap(arr[i], arr[largest]); 
  
        // Recursively heapify the affected sub-tree 
        heapify(arr, n, largest); 
    } 
} 
  
// main function to do heap sort 
void heapSort(int arr[], int n) 
{ 
    // Build heap (rearrange array) 
    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]); 
  
        // call max heapify on the reduced heap 
        heapify(arr, i, 0); 
    } 
} 
  
// A function to print array 
void printArray(int arr[], int n) 
{ 
    for (int i = 0; i < n; ++i) 
        cout << arr[i] << " "; 
    cout << "\n"; 
} 
  
// Driver program 
int main() 
{ 
    int arr[] = {4, 10, 3, 5, 1}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    heapSort(arr, n); 
  
    cout << "Sorted array is \n"; 
    printArray(arr, n); 
} 


def heapify(arr, n, i): 
    largest = i # set largest as root
    l = 2 * i + 1     # left = 2*i + 1 
    r = 2 * i + 2     # right = 2*i + 2 
  
    # See if left child of root exists and is 
    # greater than root 
    if (l < n and arr[i] < arr[l]): 
        largest = l 
  
    # See if right child of root exists and is 
    # greater than root 
    if (r < n and arr[largest] < arr[r]): 
        largest = r 
  
    # Change root, if needed 
    if (largest != i): 
        arr[i],arr[largest] = arr[largest],arr[i] # swap 
  
        # Heapify the root. 
        heapify(arr, n, largest) 
  
# function to sort an array of given size 
def heapSort(arr): 
    n = len(arr) 
  
    # Build a heap. 
    for i in range(n, -1, -1): 
        heapify(arr, n, i) 
  
    # One by one extract elements 
    for i in range(n-1, 0, -1): 
        arr[i], arr[0] = arr[0], arr[i] # swap 
        heapify(arr, i, 0) 
  
# Driver code to test above 
arr = [4, 10, 3, 5, 1]  
heapSort(arr) 
print ("Sorted array is") 
print (arr)


Python

How to implement heap sort

Heap sort is a sorting algorithm that takes the input data and sorts it in ascending or descending order. A Heap is a tree-like structure which is built using the input data. The algorithm requires 3 steps to complete the sorting procedure:   Create a heap with the input data.   Sort the elements of the heap are sorted in ascending order.   Swap the root node with the last node and delete the last node from the heap.   Following slides will assist you in understanding this concept better: 