Heap Sort

In this blog we are discussing Heap sort which is one of the famous sorting algorithms.

Basically it requires knowledge of two types of data structures i.e. Arrays and Trees.

Let's take an array [10, 5, 76, 32, 22, 34] and after sorting we get a sorted array

[5, 10, 22, 32, 34, 76].

For working of Heap sort we should consider the elements of the array as a special kind of complete binary tree called heap.

If i is the index of any element in the array then :

• The element with index 2*i + 1 will become left child.

• The element with index 2*i + 2 will become right child.

• The parent of any element is the lower bound of (i - 1) / 2.

Heap with indices

---

How It Works ?

1. Since the tree satisfies Max-Heap Property, then the largest item is stored at the root node.

2. Swap: Remove the root element and put it at the end of the array. And last element of tree at the vacant place.

3. Remove: Reduce the size of the Heap by 1.

4. Heapify: Heapify the root again so on that we have the largest element at root.

5. Process is repeated until all the items are being sorted.

---

Implementation using C:

#include <stdio.h>
 
  void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
  }
  
  void heapify(int arr[], int n, int i) {
    
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
  
    if (left < n && arr[left] > arr[largest])
      largest = left;
  
    if (right < n && arr[right] > arr[largest])
      largest = right;
  
    
    if (largest != i) {
      swap(&arr[i], &arr[largest]);
      heapify(arr, n, largest);
    }
  }
  
  
  void heapSort(int arr[], int n) {
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);
  
    
    for (int i = n - 1; i >= 0; i--) {
      swap(&arr[0], &arr[i]);
  
      // Heapify root element to get largest element at root again
      heapify(arr, i, 0);
    }
  }
  
  
  void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      printf("%d ", arr[i]);
    printf("\n");
  }
  
  
  int main() {
    int arr[] = {5, 12, 90, 15, 36, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
  
    heapSort(arr, n);
  
    printf("Sorted array is \n");
    printArray(arr, n);
  }

---

Time Complexities for all cases is O(n log n)*

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Follow Programmers Door for more.

#programming #blog #interview #heapsort