HeapSort_GL

Heap Sort is one of the best sorting methods being in-place and with no quadratic worst-case running time. It is a comparison based sorting technique based on a Binary Heap data structure. In this article, we are going to cover all these subtopics :

  1. What is Heap
  2. What is Heapsort
  3. Heapsort Pseudo-code
  4. Heapsort Algorithm
  5. Heapsort Algorithm Dry Run
  6. Heapsort Time complexity
  7. Heapsort Space complexity
  8. Heapsort in C
  9. Heapsort in JAVA
  10. Heapsort in C++
  11. Heapsort in Python
  12. Heapsort Example
  13. Which is better Mergesort or Heapsort

What is Heap

  • It is a data structure which is a complete binary tree
  • All the levels are completely filled except the last level
  • Heap has some order of values to be maintained between parents and their children
  • There are 2 variations of heap possible
    • MIN HEAP
      • Here the value of parent is always less than the value of its children
      • Hence root will be the minimum in the entire heap
    • MAX HEAP
      • Here the value of parent is always more than the value of its children
      • Hence root will be the maximum in the entire heap

What is Heapsort

  • It is one of the efficient sorting algorithm based on heap data structure
  • Here the given array to be sorted is assumed to be a heap
  • So for ith index
    • The left child will become the element present at the 2*i+1 index in the array
    • The right child will become the element present at the 2*i+2  index in the array
    • Parent of the ith index will be element present at (i-1)/2 index in the array
  • There are 2 major operations which are responsible for maintaining the heap
    • Heapify
      • This operation sets the order of values between the parent and its child
      • If we are dealing with the max heap, it will find the index having max value among the node and its children
      • If the index holding max value is not the parent, it will wap the parent with the child having the max value
      • Algo
heapify(arr , i)
	leftChild = arr [2*0 + 1];
	rightChild = arr [2*0 + 2];
    	maxIndex = max( arr[i], leftChild, rightChild)
    	if(i != maxIndex)
          		swap(arr[i], arr[maxIndex])
  • Build MAXHEAP or MINHEAP
    • This is responsible for setting parent-child order in the entire heap
    • This is the first function which is called to build the heap
    • It starts from the last parent in the tree because that is the first instance where the order may get disturbed
    • So it iterates from i=n/2-1 to 0 and call heapify on every parent
    • Algo
buildMaxHeap(arr)
	for(int i = n / 2 - 1; i >= 0; i--)
     		 heapify(arr, i);
  • In Heapsort, we deal with Maxheap.
  • As we know root will have the max value possible in the heap, we will swap it with the last element in the heap and reduce the heap size by 1.
  • Heap size is the variable that maintains the total number of elements to be considered in the heap
  • Then we call downward heapify on the root. It starts from setting the relationship between the root n d its children. If either of the children was maximum then heapify is called on it.

Heapsort Pseudo-code

  • First, call build max heap to set the heap initially
  • Once the heap is created, take the root and wap it will the last element of the heap
  • Reduce the size of the heap
  • Call max heapify of index 0 i.e, the new root of the heap

Heapsort Algorithm

Heapsort(arr)
	buildMaxHeap(arr)
	for (int i = n - 1; i >= 0; i--) {
      	  swap(&arr[0], &arr[i]);
	  heapsize--;
	  maxHeapify(arr,0);
  	}

Heapsort Algorithm Dry Run

input:

01234
2310161120

The first step – call build max heap

01234
2320161110

For i=4

01234
2011161023

After i=3

01234
1611102023

After i=2

01234
1110162023

After i=1

01234
1011162023

After i=0

01234
1011162023

Heapsort Time Complexity

  • Build max heap takes O(n/2) time
  • We are calling for heapify inside the for loop, which may take the height of the heap in the worst case for all comparison. Therefore time complexity will become O(nlogn)
  • Best Time Complexity: O(nlogn)
  • Average Time Complexity: O(nlogn)
  • Worst Time Complexity: O(nlogn)

Heapsort Space Complexity

  • No auxiliary space is required in Heapsort implementation that is we are not using any arrays, linked list, stack, queue, etc to store our elements
  • Hence space complexity is: O(1)

Heapsort in C 

#include <stdio.h>
  
  void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
  }
  
  void heapify(int arr[], int n, int i) {
    int max = i;
    int leftChild = 2 * i + 1;
    int rightChild = 2 * i + 2;
  
    if (leftChild < n && arr[leftChild] > arr[max])
      max = leftChild;
  
    if (rightChild < n && arr[rightChild] > arr[max])
      max = rightChild;
  
    if (max != i) {
      swap(&arr[i], &arr[max]);
      heapify(arr, n, max);
    }
  }
  
  void heapSort(int arr[], int n) {
    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(arr, i, 0);
    }
  }
  
  void display(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      printf("%d ", arr[i]);
    printf("\n");
  }
  
  int main() {
    int arr[] = {11, 34, 9, 5, 16, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
	
    printf("Original array:\n");
    display(arr, n);
    heapSort(arr, n);
  
    printf("Sorted array:\n");
    display(arr, n);
  }

 
Output of the program:
 Original array:
 11 34 9 5 16 10 
 Sorted array:
 5 9 10 11 16 34 

Heapsort in Java

  public class HeapSort {
  
    public void sort(int arr[]) {
      int n = arr.length;
  
      for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
      }
  
      for (int i = n - 1; i >= 0; i--) {
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;
  
        heapify(arr, i, 0);
      }
    }
  
    void heapify(int arr[], int n, int i) {
      int max = i;
      int leftChild = 2 * i + 1;
      int rightChild = 2 * i + 2;
  
      if (leftChild < n && arr[leftChild] > arr[max])
        max = leftChild;
  
      if (rightChild < n && arr[rightChild] > arr[max])
        max = rightChild;
  
      if (max != i) {
        int swap = arr[i];
        arr[i] = arr[max];
        arr[max] = swap;
  
        heapify(arr, n, max);
      }
    }
  
    static void display(int arr[]) {
      int n = arr.length;
      for (int i = 0; i < n; ++i)
        System.out.print(arr[i] + " ");
      System.out.println();
    }
  
    public static void main(String args[]) {
      int arr[] = {11, 34, 9, 5, 16, 10};
  
      HeapSort hs = new HeapSort();
      System.out.println("Original array:");
      display(arr);
	  hs.sort(arr);
  
      System.out.println("Sorted array:");
      display(arr);
    }
  }



Output of the program:
 Original array:
 11 34 9 5 16 10 
 Sorted array:
 5 9 10 11 16 34 

Heapsort in C++ 

  
  #include <iostream>
  using namespace std;
  
  void heapify(int arr[], int n, int i) {
    int max = i;
    int leftChild = 2 * i + 1;
    int rightChild = 2 * i + 2;
  
    if (leftChild < n && arr[leftChild] > arr[max])
      max = leftChild;
  
    if (rightChild < n && arr[rightChild] > arr[max])
      max = rightChild;
  
    if (max != i) {
      swap(arr[i], arr[max]);
      heapify(arr, n, max);
    }
  }
  
  void heapSort(int arr[], int n) {
    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(arr, i, 0);
    }
  }
  
  void display(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      cout << arr[i] << " ";
    cout << "\n";
  }
  
  int main() {
    int arr[] = {11, 34, 9, 5, 16, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Original array:\n";
    display(arr, n);
    heapSort(arr, n);
  
    cout << "Sorted array:\n";
    display(arr, n);
  }





Output of the program:
 Original array:
 11 34 9 5 16 10 
 Sorted array:
 5 9 10 11 16 34 

Heapsort in Python

def heapify(arr, n, i): 
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
      largest = l
    
    if r < n and arr[largest] < arr[r]:
      largest = r


    if largest != i:
      arr[i], arr[largest] = arr[largest], arr[i]
      heapify(arr, n, largest)

def heapSort(arr):
  n = len(arr)

  for i in range(n //2, -1, -1):
    heapify(arr, n, i)

  for i in range(n - 1, 0, -1): 
    arr[i], arr[0] = arr[0], arr[i]
    heapify(arr, i, 0)

arr = [11, 34, 9, 5, 16, 10] 
n = len(arr) 
print("Original array:") 
for i in range(n):       
    print("%d " % arr[i], end = '')
heapSort(arr) 
print("Sorted array:") 
for i in range(n):       
    print("%d " % arr[i], end = '')





Output of the program:
 Original array:
 11 34 9 5 16 10 
 Sorted array:
 5 9 10 11 16 34 

Heapsort Example

Example:

Find the kth largest element in the array

Input : 11 34 9 5 16 10
k= 3
Output: 11

C Code

 #include <stdio.h>
  
  void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
  }
  
  void heapify(int arr[], int n, int i) {
    int max = i;
    int leftChild = 2 * i + 1;
    int rightChild = 2 * i + 2;
  
    if (leftChild < n && arr[leftChild] > arr[max])
      max = leftChild;
  
    if (rightChild < n && arr[rightChild] > arr[max])
      max = rightChild;
  
    if (max != i) {
      swap(&arr[i], &arr[max]);
      heapify(arr, n, max);
    }
  }
  
  void heapSort(int arr[], int n, int k) {
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);
  
    for (int i = n - 1; i > k; i--) {
      swap(&arr[0], &arr[i]);
  
      heapify(arr, i, 0);
    }
    
    printf("%d ",arr[0]);
  }
  

  
  int main() {
    int arr[] = {11, 34, 9, 5, 16, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n, 3);
  }

Java Code

 public class HeapSort {
  
    public void sort(int arr[], int k) {
      int n = arr.length;
  
      for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
      }
  
      for (int i = n - 1; i > k; i--) {
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;
  
        heapify(arr, i, 0);
      }
      System.out.println(arr[0]);
    }
  
    void heapify(int arr[], int n, int i) {
      int max = i;
      int leftChild = 2 * i + 1;
      int rightChild = 2 * i + 2;
  
      if (leftChild < n && arr[leftChild] > arr[max])
        max = leftChild;
  
      if (rightChild < n && arr[rightChild] > arr[max])
        max = rightChild;
  
      if (max != i) {
        int swap = arr[i];
        arr[i] = arr[max];
        arr[max] = swap;
  
        heapify(arr, n, max);
      }
    }
  
    static void display(int arr[]) {
      int n = arr.length;
      for (int i = 0; i < n; ++i)
        System.out.print(arr[i] + " ");
      System.out.println();
    }
  
    public static void main(String args[]) {
      int arr[] = {11, 34, 9, 5, 16, 10};
  
      HeapSort hs = new HeapSort();

	  hs.sort(arr,3);

    }
  }

C++ Code

#include <iostream>
  using namespace std;
  
  void heapify(int arr[], int n, int i) {
    int max = i;
    int leftChild = 2 * i + 1;
    int rightChild = 2 * i + 2;
  
    if (leftChild < n && arr[leftChild] > arr[max])
      max = leftChild;
  
    if (rightChild < n && arr[rightChild] > arr[max])
      max = rightChild;
  
    if (max != i) {
      swap(arr[i], arr[max]);
      heapify(arr, n, max);
    }
  }
  
  void heapSort(int arr[], int n) {
    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(arr, i, 0);
    }
  }
  
  void display(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      cout << arr[i] << " ";
    cout << "\n";
  }
  
  int main() {
    int arr[] = {11, 34, 9, 5, 16, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Original array:\n";
    display(arr, n);
    heapSort(arr, n);
  
    cout << "Sorted array:\n";
    display(arr, n);
  }

Which is better Mergesort or Heapsort

  • In terms of algorithm
    • In merge sort, in every iteration, we divide the problem into 2 almost equal subproblems. Once no more dividing is possible, we start merging upwards
    • In heap sort, there are 2 major operations that basically aids heapsort that is heapify and build heap
  • In terms of time and space complexity
    • Merge sort take n extra space
    • Heap sort make all the changes in the input array itself hence space requirement is constant here

BestAverageWorstSpace
HeapO(nlogn)O(nlogn)O(nlogn)O(1)
MergeO(nlogn)O(nlogn)O(nlogn)O(n)
  • In terms of speed
    • Heapsort is a bit slower than merge sort
  • In terms of in-place
    • In-place states that the algorithm is in-place if it does not need extra memory barring some variable creation which counts to constant space.
    • Heap sort does not require any auxiliary memory but merge sort is out place.
  • In terms of stability
    • Stability states that the algorithm is stable if the relative ordering of the same elements in the input and output array remains the same.
    • Merge sort is stable algorithms but heap sort is not as swapping may cost stability.

This brings us to the end of this article where we learned about heap sort. To get a free course on data structures and algorithms, click on the banner below. Also, visit the great learning academy to see all the free courses we are providing.

heap sort
0

LEAVE A REPLY

Please enter your comment!
Please enter your name here

3 + 12 =