Heap sort

Introduction:

This is a comparison based sorting algorithm which makes use of heap concept using arrays and max-heapify operation on elements of array. This algorithm is better understood when you visualize it through binary trees ( showing heap structure )..

Problem Statement:

Sort an array of n integers

Algorithm

1. First step is to make a heap of numbers from the array such that every element is bigger than all the elements below it in the heap

2. Looking at this we can see that top one is the largest. replace it with an element at the bottom of the heap and put it at the end of the array. Then decrease the array size by one

3. Now just recursively push the top element if there is a larger element as its children in the next row of the heap.Do this till we reach leaf (bottom) . This is called max heapifying of top element.

4. Repeat steps 2 and 3 till heap is empty and we get the sorted array.

Pseudo code :

heap_sort(a[],  n):
    heap_size = n-1
    for i = heap_size/2 to 0
        max_heapify(a, i , heap_size)
    
    for i = n-1 to 0
        swap(a[i], a[0])
        heap_size --
        max_heapify(a,0,heap_size) // puts max element at the end

    
max_heapify(a, index, heap_size):	
    left = 2*index
    right = left+1
    largest = index
    if left <= heap_size and a[left] > a[largest]:
        largest = left
    if right <= heap_size and a[right] > a[largest]:
        largest = right
    if largest != index : // it means a[index] is not the largest
        swap(a[largest],a[index])
        max_heapify(a, largest,heap_size)

Code :

    #include <bits/stdc++.h>
    using namespace std;
    
    #define Parent(i) i >> 1      // i/2
    #define Left(i) i << 1        // 2*i
    #define Right(i) (i << 1) + 1 // 2*i+1
    
    void max_heapify(int a[], int index, int heap_size)
    {
        int left = Left(index);   //left child
        int right = Right(index); // right child
        int largest = index;
        if (left <= heap_size && a[left] > a[largest]) // compare a[left] & a[largest]
        {
            largest = left;
        }
        if (right <= heap_size && a[right] > a[largest]) // compare a[right] & a[largest]
        {
            largest = right;
        }
        if (largest != index) // 'index' is not 'largest'
        {
            swap(a[largest], a[index]);
            max_heapify(a, largest, heap_size); // heapify the child with which swap occurred.
        }
        //index element is largest hence it satisfies heap property.
    }
    
    void build_max_heap(int a[], int heap_size)
    {
        for (int i = (heap_size / 2); i >= 0; i--) // a[(heap_size/2)+1....heap_size] are leaf nodes
        {
            max_heapify(a, i, heap_size);
        }
    }
    
    void heap_sort(int a[], int n)
    {
    
        int heap_size = n - 1;        //last element index
        build_max_heap(a, heap_size); // building max heap -->  a[i] >= Left(i) & a[i] >= Right[i]
        // parent is greater than equal to its children.
    
        for (int i = n - 1; i > 0; i--)
        {
            swap(a[i], a[0]);             // swap last element(a[i]) with maximum element(a[0])
            heap_size--;                  // like linear sort where max goes to end and we decrease size by 1. here we get max in O(1) time
            max_heapify(a, 0, heap_size); // a[0] may not satisfy heap property so heapify it. O(log heap_size)
        }
    }
    
    int main()
    {
        int n;
        cout << "Enter n: ";
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        heap_sort(a, n);
        for (int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
        printf("\n");
    }

Complexity Analysis :

Time complexity is \(O(nlogn)\)

since heap is a binary tree having height of \(logn\). So max-heapify takes \(O(logn)\) time

We do max-heapify n times. Hence complexity is \(O(nlogn)\).