Heapsort in Java

Yasin Cakal

Heapsort is an efficient sorting algorithm that works by creating a max-heap data structure from an array of elements. The algorithm then uses the heap structure to sort the elements in the array. Heapsort is often used in practice because of its lower time complexity and its ability to sort both ascending and descending order. In this article, we will discuss the Heapsort algorithm in detail, its time complexity, space complexity, and provide a Java implementation of the algorithm.

What is Heapsort?

Heapsort is an efficient sorting algorithm that works by creating a max-heap data structure from an array of elements. A max-heap is a complete binary tree in which each node is greater than its children. The algorithm then uses the heap structure to sort the elements in the array. Heapsort is often used in practice because of its lower time complexity and its ability to sort both ascending and descending order.

How does Heapsort Work?

Heapsort works by first creating a max-heap from the array of elements. The algorithm then starts by selecting the root node of the max-heap, which is the highest value in the array. The root node is then swapped with the last element in the array and the heap is then reduced by one. This process is repeated until all the elements in the array have been sorted.

Heapsort Algorithm

The following algorithm is used to sort an array of elements using Heapsort:

Create a max-heap from the array of elements.
Select the root node of the max-heap, which is the highest value in the array.
Swap the root node with the last element in the array.
Reduce the size of the heap by one.
Repeat steps 2-4 until all the elements in the array have been sorted.

Java Implementation

The following Java program implements the Heapsort algorithm:

public class HeapSort 
{ 
    public void sort(int arr[]) 
    { 
        int n = arr.length; 
  
        // Build heap (rearrange array) 
        for (int i = n / 2 - 1; i >= 0; i--) 
            heapify(arr, n, i); 
  
        // One by one extract an element from heap 
        for (int i=n-1; i>=0; i--) 
        { 
            // Move current root to end 
            int temp = arr[0]; 
            arr[0] = arr[i]; 
            arr[i] = temp; 
  
            // call max heapify on the reduced heap 
            heapify(arr, i, 0); 
        } 
    } 
  
    // To heapify a subtree rooted with node i which is 
    // an index in arr[]. n is size of heap 
    void heapify(int arr[], int n, int i) 
    { 
        int largest = i; // Initialize largest as root 
        int l = 2*i + 1; // left = 2*i + 1 
        int r = 2*i + 2; // right = 2*i + 2 
  
        // If left child is larger than root 
        if (l < n && arr[l] > arr[largest]) 
            largest = l; 
  
        // If right child is larger than largest so far 
        if (r < n && arr[r] > arr[largest]) 
            largest = r; 
  
        // If largest is not root 
        if (largest != i) 
        { 
            int swap = arr[i]; 
            arr[i] = arr[largest]; 
            arr[largest] = swap; 
  
            // Recursively heapify the affected sub-tree 
            heapify(arr, n, largest); 
        } 
    } 
  
    /* A utility function to print array of size n */
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i]+" "); 
        System.out.println(); 
    } 
  
    // Driver program 
    public static void main(String args[]) 
    { 
        int arr[] = {12, 11, 13, 5, 6, 7}; 
        int n = arr.length; 
  
        HeapSort ob = new HeapSort(); 
        ob.sort(arr); 
  
        System.out.println("Sorted array is"); 
        printArray(arr); 
    } 
}

Time and Space Complexity of Heapsort

The time complexity of Heapsort is O(n log n). This means that the algorithm takes O(n log n) time to sort an array of n elements. The worst case time complexity of Heapsort is also O(n log n).

The space complexity of the Heapsort algorithm is O(1). This means that the algorithm does not require any additional memory for its operation and thus, has a constant space complexity of O(1).

Conclusion

In conclusion, Heapsort is an efficient sorting algorithm that works by creating a max-heap data structure from an array of elements. The algorithm then uses the heap structure to sort the elements in the array. Heapsort is often used in practice because of its lower time complexity and its ability to sort both ascending and descending order. The time complexity of Heapsort is O(n log n) and the space complexity is O(1).

Exercises

Write a Java program to implement the Heapsort algorithm on an array of integers.

public class HeapSort 
{ 
    public void sort(int arr[]) 
    { 
        int n = arr.length; 
  
        // Build heap (rearrange array) 
        for (int i = n / 2 - 1; i >= 0; i--) 
            heapify(arr, n, i); 
  
        // One by one extract an element from heap 
        for (int i=n-1; i>=0; i--) 
        { 
            // Move current root to end 
            int temp = arr[0]; 
            arr[0] = arr[i]; 
            arr[i] = temp; 
  
            // call max heapify on the reduced heap 
            heapify(arr, i, 0); 
        } 
    } 
  
    // To heapify a subtree rooted with node i which is 
    // an index in arr[]. n is size of heap 
    void heapify(int arr[], int n, int i) 
    { 
        int largest = i; // Initialize largest as root 
        int l = 2*i + 1; // left = 2*i + 1 
        int r = 2*i + 2; // right = 2*i + 2 
  
        // If left child is larger than root 
        if (l < n && arr[l] > arr[largest]) 
            largest = l; 
  
        // If right child is larger than largest so far 
        if (r < n && arr[r] > arr[largest]) 
            largest = r; 
  
        // If largest is not root 
        if (largest != i) 
        { 
            int swap = arr[i]; 
            arr[i] = arr[largest]; 
            arr[largest] = swap; 
  
            // Recursively heapify the affected sub-tree 
            heapify(arr, n, largest); 
        } 
    } 
  
    /* A utility function to print array of size n */
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i]+" "); 
        System.out.println(); 
    } 
  
    // Driver program 
    public static void main(String args[]) 
    { 
        int arr[] = {12, 11, 13, 5, 6, 7}; 
        int n = arr.length; 
  
        HeapSort ob = new HeapSort(); 
        ob.sort(arr); 
  
        System.out.println("Sorted array is"); 
        printArray(arr); 
    } 
}

What is the time complexity of Heapsort?