heapsort

1#include <iostream>
2 
3using namespace std;
4 
5
6void heapify(int arr[], int n, int i)
7{
8    int largest = i; 
9    int l = 2 * i + 1;
10    int r = 2 * i + 2;
11 
12    
13    if (l < n && arr[l] > arr[largest])
14        largest = l;
15 
16    
17    if (r < n && arr[r] > arr[largest])
18        largest = r;
19 
20    
21    if (largest != i) {
22        swap(arr[i], arr[largest]);
23 
24    
25        heapify(arr, n, largest);
26    }
27}
28 
29
30void heapSort(int arr[], int n)
31{
32
33    for (int i = n / 2 - 1; i >= 0; i--)
34        heapify(arr, n, i);
35 
36
37    for (int i = n - 1; i > 0; i--) {
38       
39        swap(arr[0], arr[i]);
40        heapify(arr, i, 0);
41    }
42}
43 
44
45void printArray(int arr[], int n)
46{
47    for (int i = 0; i < n; ++i)
48        cout << arr[i] << " ";
49    cout << "\n";
50}
51 
52
53int main()
54{
55    int arr[] = { 12, 11, 13, 5, 6, 7 };
56    int n = sizeof(arr) / sizeof(arr[0]);
57 
58    heapSort(arr, n);
59 
60    cout << "Sorted array is \n";
61    printArray(arr, n);
62}

1// Heap Sort in C
2  
3  #include <stdio.h>
4  
5  // Function to swap the the position of two elements
6  void swap(int *a, int *b) {
7    int temp = *a;
8    *a = *b;
9    *b = temp;
10  }
11  
12  void heapify(int arr[], int n, int i) {
13    // Find largest among root, left child and right child
14    int largest = i;
15    int left = 2 * i + 1;
16    int right = 2 * i + 2;
17  
18    if (left < n && arr[left] > arr[largest])
19      largest = left;
20  
21    if (right < n && arr[right] > arr[largest])
22      largest = right;
23  
24    // Swap and continue heapifying if root is not largest
25    if (largest != i) {
26      swap(&arr[i], &arr[largest]);
27      heapify(arr, n, largest);
28    }
29  }
30  
31  // Main function to do heap sort
32  void heapSort(int arr[], int n) {
33    // Build max heap
34    for (int i = n / 2 - 1; i >= 0; i--)
35      heapify(arr, n, i);
36  
37    // Heap sort
38    for (int i = n - 1; i >= 0; i--) {
39      swap(&arr[0], &arr[i]);
40  
41      // Heapify root element to get highest element at root again
42      heapify(arr, i, 0);
43    }
44  }
45  
46  // Print an array
47  void printArray(int arr[], int n) {
48    for (int i = 0; i < n; ++i)
49      printf("%d ", arr[i]);
50    printf("\n");
51  }
52  
53  // Driver code
54  int main() {
55    int arr[] = {1, 12, 9, 5, 6, 10};
56    int n = sizeof(arr) / sizeof(arr[0]);
57  
58    heapSort(arr, n);
59  
60    printf("Sorted array is \n");
61    printArray(arr, n);
62  }

1// @see https://www.youtube.com/watch?v=H5kAcmGOn4Q
2
3function heapify(list, size, index) {
4    let largest = index;
5    let left = index * 2 + 1;
6    let right = left + 1;
7    if (left < size && list[left] > list[largest]) {
8        largest = left;
9    }
10    if (right < size && list[right] > list[largest]) {
11        largest = right;
12    }
13    if (largest !== index) {
14        [list[index], list[largest]] = [list[largest], list[index]];
15        heapify(list, size, largest);
16    }
17    return list;
18}
19
20function heapsort(list) {
21    const size = list.length;
22    let index = ~~(size / 2 - 1);
23    let last = size - 1;
24    while (index >= 0) {
25        heapify(list, size, --index);
26    }
27    while (last >= 0) {
28        [list[0], list[last]] = [list[last], list[0]];
29        heapify(list, --last, 0);
30    }
31    return list;
32}
33
34heapsort([4, 7, 2, 6, 4, 1, 8, 3]);

1Implementation of heap sort in C++:
2
3#include <bits/stdc++.h>
4using namespace std;
5
6// To heapify a subtree rooted with node i which is
7// Heapify:- A process which helps regaining heap properties in tree after removal 
8void heapify(int A[], int n, int i)
9{
10   int largest = i; // Initialize largest as root
11   int left_child = 2 * i + 1; // left = 2*i + 1
12   int right_child = 2 * i + 2; // right = 2*i + 2
13
14   // If left child is larger than root
15   if (left_child < n && A[left_child] > A[largest])
16       largest = left_child;
17
18   // If right child is larger than largest so far
19   if (right_child < n && A[right_child] > A[largest])
20       largest = right_child;
21
22   // If largest is not root
23   if (largest != i) {
24       swap(A[i], A[largest]);
25
26       // Recursively heapify the affected sub-tree
27       heapify(A, n, largest);
28   }
29}
30
31// main function to do heap sort
32void heap_sort(int A[], int n)
33{
34   // Build heap (rearrange array)
35   for (int i = n / 2 - 1; i >= 0; i--)
36       heapify(A, n, i);
37
38   // One by one extract an element from heap
39   for (int i = n - 1; i >= 0; i--) {
40       // Move current root to end
41       swap(A[0], A[i]);
42
43       // call max heapify on the reduced heap
44       heapify(A, i, 0);
45   }
46}
47
48/* A  function to print sorted Array */
49void printArray(int A[], int n)
50{
51   for (int i = 0; i < n; ++i)
52       cout << A[i] << " ";
53   cout << "\n";
54}
55
56// Driver program
57int main()
58{
59   int A[] = { 22, 19, 3, 25, 26, 7 }; // array to be sorted
60   int n = sizeof(A) / sizeof(A[0]); // n is size of array
61
62   heap_sort(A, n);
63
64   cout << "Sorted array is \n";
65   printArray(A, n);
66}

1void heapify(int arr[], int n, int i) {
2  // Find largest among root, left child and right child
3  int largest = i;
4  int left = 2 * i + 1;
5  int right = 2 * i + 2;
6
7  if (left < n && arr[left] > arr[largest])
8    largest = left;
9
10  if (right < n && arr[right] > arr[largest])
11    largest = right;
12
13    // Swap and continue heapifying if root is not largest
14    if (largest != i) {
15      swap(&arr[i], &arr[largest]);
16      heapify(arr, n, largest);
17  }
18}

1#include <iostream>
2
3using namespace std;
4void swap(int*,int*);
5void heapify(int arr[],int n,int index)
6{
7    int left=2*index+1;
8    int right=left+1;
9    int max=index;
10    if(left<n&&arr[left]>arr[max])
11    {
12        max=left;
13    }
14    if(right<n&&arr[right]>arr[max])
15    {
16        max=right;
17    }
18    if(index!=max)
19    {
20        swap(&arr[index],&arr[max]);
21        heapify(arr,n,max);
22    }
23}
24void buildheap(int arr[],int n)
25{
26    for(int i=(n/2);i>=0;i--)
27    {
28        heapify(arr,n,i);
29    }
30}
31
32void heapsort(int arr[],int n)
33{
34    buildheap(arr,n);
35    int l=n-1;
36    while(l>0)
37    {
38        swap(&arr[0],&arr[l]);
39        l--;
40        n--;
41        heapify(arr,n,0);
42    }
43}
44void disp(int arr[],int n)
45{
46    for(int i=0;i<n;i++)
47    {
48        cout<<arr[i]<<" ";
49    }
50    cout<<endl;
51}
52
53int main()
54{
55    int n;
56    cout<<"enter the size of the array:"<<endl;
57    cin>>n;
58    int a[n];
59
60    cout<<"enter the elements of the array:"<<endl;
61    for(int i=0;i<n;i++)
62    {
63        cin>>a[i];
64    }
65    cout<<"array before sorting:"<<endl;
66    for(int i=0;i<n;i++)
67    {
68        cout<<a[i]<<" ";
69    }
70    cout<<endl;
71    //buildheap(a,n);
72    //disp(a,n);
73    cout<<"array after sorting:"<<endl;
74    heapsort(a,n);
75    disp(a,n);
76    return 0;
77}
78void swap(int*a,int*b)
79{
80    int temp=*a;
81    *a=*b;
82    *b=temp;
83}
84