fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Heapsort
  4. //
  5. //  Created by Himanshu on 25/09/21.
  6. //
  7.  
  8. #include <iostream>
  9. using namespace std;
  10.  
  11. void printArray (int arr[], int n) {
  12.     for (int i=0; i<n; i++) {
  13.         cout<<arr[i]<<" ";
  14.     }
  15.     cout<<endl;
  16. }
  17.  
  18. void MaxHeapify(int arr[], int i, int heapSize) {
  19.     int l, r, large;
  20.     l = 2*i + 1;
  21.     r = 2*i + 2;
  22.     if (l < heapSize && arr[l] > arr[i]) {
  23.         large = l;
  24.     } else {
  25.         large = i;
  26.     }
  27.  
  28.     if (r < heapSize && arr[r] > arr[large]) {
  29.         large = r;
  30.     }
  31.  
  32.     //Assuring heap property
  33.     if (large != i) {
  34.         swap (arr[i], arr[large]);
  35.         MaxHeapify(arr, large, heapSize);
  36.     }
  37. }
  38.  
  39. void BuildHeap(int arr[], int n) {
  40.     int k = (n/2)-1;
  41.     for (int i=k; i>=0; i--) {
  42.         MaxHeapify(arr, i, n);
  43.     }
  44. }
  45.  
  46. void Heapsort (int arr[], int n) {
  47.     BuildHeap(arr, n);
  48.     int j = 1, N = n;
  49.  
  50.     for (int i=n-1; i>=0; i--) {
  51.         swap(arr[0], arr[i]);
  52.         n--;
  53.  
  54.         MaxHeapify(arr, 0, n);
  55.         printf("Array after %d Max-Heapify\n", j++);
  56.         printArray(arr, N);
  57.     }
  58. }
  59.  
  60. int main() {
  61.     int arr[] = {8, 3, 9, 2, 16, 10, 14, 7, 4};
  62.     int n = sizeof(arr)/sizeof(arr[0]);
  63.  
  64.     cout<<"Initial Array:"<<endl;
  65.     printArray(arr, n);
  66.     cout<<endl;
  67.  
  68.     Heapsort(arr, n);
  69.  
  70.     cout<<endl<<"Array after Heapsort:"<<endl;
  71.     printArray(arr, n);
  72.  
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 5476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Initial Array:
8 3 9 2 16 10 14 7 4 

Array after 1 Max-Heapify
14 8 10 7 3 4 9 2 16 
Array after 2 Max-Heapify
10 8 9 7 3 4 2 14 16 
Array after 3 Max-Heapify
9 8 4 7 3 2 10 14 16 
Array after 4 Max-Heapify
8 7 4 2 3 9 10 14 16 
Array after 5 Max-Heapify
7 3 4 2 8 9 10 14 16 
Array after 6 Max-Heapify
4 3 2 7 8 9 10 14 16 
Array after 7 Max-Heapify
3 2 4 7 8 9 10 14 16 
Array after 8 Max-Heapify
2 3 4 7 8 9 10 14 16 
Array after 9 Max-Heapify
2 3 4 7 8 9 10 14 16 

Array after Heapsort:
2 3 4 7 8 9 10 14 16
https://ideone.com/LbcUZK
language:
C++ 4.3.2 (gcc-4.3.2)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!