HeapSort implementation in Java/C++

Heapsort

Heapsort is a sorting algorithm that uses Binary heaps for the purpose of sorting. Heaps can be of two types, min-heap and max heap.

Heapsort is an improved version of selection sort.

For this tutorial we will be using max heap for implementing Heapsort.

Max heap follows the property that the parent element is always greater than its children. That means in a max heap the root is always the maximum of all the elements. Heapsort uses this property to arrange elements in a sorted manner.

This tutorial assumes that you have a basic understanding of heaps. In case you want to learn about heaps, you can go over this tutorial on heaps and its implementation. (add link)

Algorithm

The algorithm for Heapsort is as follows :

  1. Build a max heap from the input array.
  2. Replace root (maximum) with the last item of the heap.
  3. Reduce the size of the heap by 1.
  4. Heapify the root of the tree by calling DownHeapify
  5. Repeat step 2 to 4 while the size of the heap is greater than 1.

At each iteration, we are taking the maximum element and placing it at the end of the heap. Then we are reducing the size of the heap. As we carry on this process, we are sorting the array from the end.

We will be calling the function downheapify( ) to make sure that the heap property is satisfied after reducing the size.

HeapSort Implementation

To heapify the array we use a recursive function that moves from the root towards the leaf nodes. This function at each node compares the parent to its children. If the value of parent node is less than its children nodes, it swaps the values. This swap makes sure that the max heap property is satisfied.

After performing the swap if further calls the downheapify function on the children.

This function needs to be called every time an element is added or deleted from the heap.

In a heap the position of children are given by :

Left child : (2*i) + 1
Right child : (2*i) + 2 

The code for downheapify is as follows :

static void downheapify(int arr[], int n, int i)
    {
        int largest = i;
        int l = 2*i + 1;
        int r = 2*i + 2;

        // finding the maximum of left and right
        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        //swapping if child >parent
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;


            downheapify(arr, n, largest);
        }
    }

To sort an array, we first need to create a heap out of it. This is done by the following lines of code :

  for (int i = n / 2 - 1; i >= 0; i--)
            downheapify(arr, n, i);

We only need to consider non-leaf nodes while calling downheapify, since leaf nodes already satisfy the heap property.

The next step is to extract an element from the root position and swap it with the last position of the heap. Once this is done, we reduce the size of the heap and again call downheapify. The lines of code that do this are :

 for (int i=n-1; i>0; i--)
        {
          // swap the last element with root
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

          // i is the size of the reduced heap
           downheapify(arr, i, 0);
        }

The complete code for sort function is :

 public static void sort(int arr[])
    {
        int n = arr.length;

      //build heap by calling heapify on non leaf elements
        for (int i = n / 2 - 1; i >= 0; i--)
            downheapify(arr, n, i);

     //extract elements from the root and call healpify
        for (int i=n-1; i>0; i--)
        {
          // swap the last element with root
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // i is the size of the reduced heap
            downheapify(arr, i, 0);
        }
    }

Apart from these two functions, we need a function to print the array as well.

The print function is as follows :

 static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

Using these three functions we can successfully implement Heapsort.

Complete Code

The complete code for Heapsort is as follows :

1. Heap Sort in Java

package com.JournalDev;

public class Main {
    static void downheapify(int arr[], int n, int i)
    {
        int largest = i;
        int l = 2*i + 1;
        int r = 2*i + 2;

        // finding the maximum of left and right
        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        //swapping if child >parent
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;


            downheapify(arr, n, largest);
        }
    }

    public static void sort(int arr[])
    {
        int n = arr.length;

      //build heap by calling heapify on non leaf elements
        for (int i = n / 2 - 1; i >= 0; i--)
            downheapify(arr, n, i);

     //extract elements from the root and call healpify
        for (int i=n-1; i>0; i--)
        {
          // swap the last element with root
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // i is the size of the reduced heap
            downheapify(arr, i, 0);
        }
    }
    static void printArray(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[] arg)
    {
        int arr[] = {1, 10, 2, 3, 4, 1, 2, 100,23, 2};
        int n = arr.length;
        sort(arr);
        System.out.println("Sorted array is");
        printArray(arr);


    }

}

2. Heap Sort in C++

#include <iostream> 
  
using namespace std; 

void downheapify(int arr[], int n, int i) 
{ 
    int largest = i; 
    int l = 2*i + 1; 
    int r = 2*i + 2; 
  
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 
  
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 
 
    if (largest != i) 
    { 
         swap(arr[i], arr[largest]);           downheapify(arr, n, largest); 
    } 
} 
  

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 printArray(int arr[], int n) 
{ 
    for (int i=0; i<n; ++i) 
        cout << arr[i] << " "; 
    cout << "\n"; 
} 
  

int main() 
{ 
   int arr[] = {1, 10, 2, 3, 4, 1, 2, 100,23, 2}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    heapSort(arr, n); 
  
    cout << "Sorted array is \n"; 
    printArray(arr, n); 
} 
Output : 

Sorted array is
1 1 2 2 2 3 4 10 23 100 
Heapsort

Conclusion

This is how you can implement Heapsort in Java/C++. The time complexity of Heapsort is O(log(n)). Heapsort is a better sorting algorithm as compared to bubble sort, insertion sort, selection sort and even quick sort.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages