// C++ program for implementation  // of Iterative Heap Sort #include    using namespace std; // function build Max Heap where value  // of each child is always smaller // than value of their parent void buildMaxHeap(int arr[] int n)  {   for (int i = 1; i < n; i++)   {  // if child is bigger than parent  if (arr[i] > arr[(i - 1) / 2])   {  int j = i;    // swap child and parent until  // parent is smaller  while (arr[j] > arr[(j - 1) / 2])   {  swap(arr[j] arr[(j - 1) / 2]);  j = (j - 1) / 2;  }  }  } } void heapSort(int arr[] int n)  {  buildMaxHeap(arr n);  for (int i = n - 1; i > 0; i--)  {  // swap value of first indexed   // with last indexed   swap(arr[0] arr[i]);    // maintaining heap property  // after each swapping  int j = 0 index;    do  {  index = (2 * j + 1);    // if left child is smaller than   // right child point index variable   // to right child  if (arr[index] < arr[index + 1] &&  index < (i - 1))  index++;    // if parent is smaller than child   // then swapping parent with child   // having higher value  if (arr[j] < arr[index] && index < i)  swap(arr[j] arr[index]);    j = index;    } while (index < i);  } } // Driver Code to test above int main()  {  int arr[] = {10 20 15 17 9 21};  int n = sizeof(arr) / sizeof(arr[0]);    printf('Given array: ');  for (int i = 0; i < n; i++)  printf('%d ' arr[i]);    printf('nn');   heapSort(arr n);  // print array after sorting  printf('Sorted array: ');  for (int i = 0; i < n; i++)  printf('%d ' arr[i]);  return 0; } 

// C program for implementation // of Iterative Heap Sort #include  // function build Max Heap where value // of each child is always smaller // than value of their parent void buildMaxHeap(int arr[] int n) {  for (int i = 1; i < n; i++)  {  // if child is bigger than parent  if (arr[i] > arr[(i - 1) / 2])  {  int j = i;    // swap child and parent until  // parent is smaller  while (arr[j] > arr[(j - 1) / 2])  {  int temp=arr[j];  arr[j]=arr[(j-1)/2];  arr[(j-1)/2]=temp;  j = (j - 1) / 2;  }  }  } } void heapSort(int arr[] int n) {  buildMaxHeap(arr n);  for (int i = n - 1; i > 0; i--)  {  // swap value of first indexed  // with last indexed  int temp=arr[0];  arr[0]=arr[i];  arr[i]=temp;    // maintaining heap property  // after each swapping  int j = 0 index;    do  {  index = (2 * j + 1);    // if left child is smaller than  // right child point index variable  // to right child  if (arr[index] < arr[index + 1] &&  index < (i - 1))  index++;    // if parent is smaller than child  // then swapping parent with child  // having higher value  if (arr[j] < arr[index] && index < i)  {  int tem1=arr[j];  arr[j]=arr[index];  arr[index]=tem1;  }    j = index;    } while (index < i);  } } // Driver Code to test above int main() {  int arr[] = {10 20 15 17 9 21};  int n = sizeof(arr) / sizeof(arr[0]);    printf('Given array: ');  for (int i = 0; i < n; i++)  printf('%d ' arr[i]);    printf('nn');  heapSort(arr n);  // print array after sorting  printf('Sorted array: ');  for (int i = 0; i < n; i++)  printf('%d ' arr[i]);  return 0; } 

// Java implementation of Iterative Heap Sort  public class HeapSort {  // function build Max Heap where value  // of each child is always smaller  // than value of their parent  static void buildMaxHeap(int arr[] int n)  {  for (int i = 1; i < n; i++)  {  // if child is bigger than parent  if (arr[i] > arr[(i - 1) / 2])  {  int j = i;  // swap child and parent until  // parent is smaller  while (arr[j] > arr[(j - 1) / 2])  {  swap(arr j (j - 1) / 2);  j = (j - 1) / 2;  }  }  }  }  static void heapSort(int arr[] int n)  {  buildMaxHeap(arr n);  for (int i = n - 1; i > 0; i--)  {  // swap value of first indexed  // with last indexed  swap(arr 0 i);  // maintaining heap property  // after each swapping  int j = 0 index;  do  {  index = (2 * j + 1);  // if left child is smaller than  // right child point index variable  // to right child  if (index < (i - 1) && arr[index] < arr[index + 1])  index++;  // if parent is smaller than child  // then swapping parent with child  // having higher value  if (index < i && arr[j] < arr[index])  swap(arr j index);  j = index;  } while (index < i);  }  }  public static void swap(int[] a int i int j) {  int temp = a[i];  a[i]=a[j];  a[j] = temp;  }  /* A utility function to print array of size n */  static void printArray(int arr[])  {  int n = arr.length;  for (int i = 0; i < n; i++)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver program  public static void main(String args[])  {  int arr[] = {10 20 15 17 9 21};  int n = arr.length;  System.out.print('Given array: ');  printArray(arr);  heapSort(arr n);  System.out.print('Sorted array: ');  printArray(arr);  } } 

# Python3 program for implementation  # of Iterative Heap Sort  # function build Max Heap where value  # of each child is always smaller  # than value of their parent  def buildMaxHeap(arr n): for i in range(n): # if child is bigger than parent  if arr[i] > arr[int((i - 1) / 2)]: j = i # swap child and parent until  # parent is smaller  while arr[j] > arr[int((j - 1) / 2)]: (arr[j] arr[int((j - 1) / 2)]) = (arr[int((j - 1) / 2)] arr[j]) j = int((j - 1) / 2) def heapSort(arr n): buildMaxHeap(arr n) for i in range(n - 1 0 -1): # swap value of first indexed  # with last indexed  arr[0] arr[i] = arr[i] arr[0] # maintaining heap property  # after each swapping  j index = 0 0 while True: index = 2 * j + 1 # if left child is smaller than  # right child point index variable  # to right child  if (index < (i - 1) and arr[index] < arr[index + 1]): index += 1 # if parent is smaller than child  # then swapping parent with child  # having higher value  if index < i and arr[j] < arr[index]: arr[j] arr[index] = arr[index] arr[j] j = index if index >= i: break # Driver Code if __name__ == '__main__': arr = [10 20 15 17 9 21] n = len(arr) print('Given array: ') for i in range(n): print(arr[i] end = ' ') print() heapSort(arr n) # print array after sorting  print('Sorted array: ') for i in range(n): print(arr[i] end = ' ') # This code is contributed by PranchalK 

// C# implementation of Iterative Heap Sort  using System;   class HeapSort  { // function build Max Heap where value // of each child is always smaller // than value of their parent static void buildMaxHeap(int []arr int n) {  for (int i = 1; i < n; i++)  {  // if child is bigger than parent  if (arr[i] > arr[(i - 1) / 2])  {  int j = i;    // swap child and parent until  // parent is smaller  while (arr[j] > arr[(j - 1) / 2])  {  swap(arr j (j - 1) / 2);  j = (j - 1) / 2;  }  }  } } static void heapSort(int []arr int n) {  buildMaxHeap(arr n);  for (int i = n - 1; i > 0; i--)  {    // swap value of first indexed  // with last indexed  swap(arr 0 i);    // maintaining heap property  // after each swapping  int j = 0 index;    do  {  index = (2 * j + 1);    // if left child is smaller than  // right child point index variable  // to right child  if (index < (i - 1) && arr[index] <   arr[index + 1])  index++;    // if parent is smaller than child  // then swapping parent with child  // having higher value  if (index < i && arr[j] < arr[index])  swap(arr j index);    j = index;    } while (index < i);  } } public static void swap(int[] a int i int j)  {  int temp = a[i];  a[i] = a[j];  a[j] = temp; } /* A utility function to print array of size n */ static void printArray(int []arr) {  int n = arr.Length;  for (int i = 0; i < n; i++)  Console.Write(arr[i] + ' ');  Console.WriteLine(); } // Driver Code public static void Main(String []args) {  int []arr = {10 20 15 17 9 21};  int n = arr.Length;  Console.Write('Given array: ');  printArray(arr);  heapSort(arr n);  Console.Write('Sorted array: ');  printArray(arr); } } // This code is contributed by Princi Singh 

<script> // javascript program for implementation  // of Iterative Heap Sort function swap(arr i j) {  let temp = arr[i];  arr[i] = arr[j];  arr[j] = temp; } // function build Max Heap where value  // of each child is always smaller // than value of their parent function buildMaxHeap(arr n) {  for(let i=1;i<n;i++)  {  // if child is bigger than parent  if (arr[i] > arr[(i - 1) / 2])   {  let j = i;    // swap child and parent until  // parent is smaller  while (arr[j] > arr[(j - 1) / 2])   {  swap(arrj(j-1)/2);  j = (j - 1) / 2;  }  }  } }   function heapSort(arr n) {    buildMaxHeap(arrn);    for (let i = n - 1; i > 0; i--)  {  // swap value of first indexed   // with last indexed   swap(arr0i);    // maintaining heap property  // after each swapping  let j = 0 index;    do  {  index = (2 * j + 1);    // if left child is smaller than   // right child point index variable   // to right child  if (arr[index] < arr[index + 1] && index < (i - 1))  index++;    // if parent is smaller than child   // then swapping parent with child   // having higher value  if (arr[j] < arr[index] && index < i)  swap(arr j index);    j = index;    } while (index < i);  } }   // Driver Code to test above let arr = [10 20 15 17 9 21]; let n = arr.length; document.write('Given array : '); for (let i = 0; i < n; ++i)  document.write(arr[i]+' ');   document.write('  
'); heapSort(arrn); // print array after sorting document.write('Sorted array : '); for (let i = 0; i < n; ++i)  document.write(arr[i]+' ');   // This code is contributed by aditya942003patil   </script>