Back to Course

Data Structures and Algorithms with Java

0% Complete
0/0 Steps
  1. Introduction to Data Structures and Algorithms
    Overview of Data Structures and Algorithms with Java
  2. Importance of Data Structures and Algorithms in Programming with Java
  3. How to Choose the Right Data Structure or Algorithm for a given Problem with Java
  4. Basic Java Concepts Review
    Variables and Data Types in Java
  5. Control Flow Statements in Java
  6. Classes and Objects in Java
  7. Methods and Constructors in Java
  8. Basic Input and Output in Java
  9. Data Structures
    Arrays in Java
  10. Stacks and Queues in Java
  11. Linked Lists in Java
  12. Hash Tables in Java
  13. Trees in Java
  14. Types of Trees
    Binary Search Trees in Java
  15. Cartesian Trees in Java
  16. B-Trees in Java
  17. Red-Black Trees in Java
  18. Splay Trees in Java
  19. AVL Trees in Java
  20. KD Trees in Java
  21. Min Heap in Java
  22. Max Heap in Java
  23. Trie Trees in Java
  24. Suffix Trees in Java
  25. Sorting Algorithms
    Quicksort in Java
  26. Mergesort in Java
  27. Timsort in Java
  28. Heapsort in Java
  29. Bubble Sort in Java
  30. Insertion Sort in Java
  31. Selection Sort in Java
  32. Tree Sort in Java
  33. Shell Sort in Java
  34. Bucket Sort in Java
  35. Radix Sort in Java
  36. Counting Sort in Java
  37. Cubesort in Java
  38. Searching Algorithms
    Linear Search in Java
  39. Binary Search in Java
  40. Graph Algorithms
    Breadth First Search (BFS) in Java
  41. Depth First Search (DFS) in Java
  42. Dijkstra's Algorithm in Java
  43. Algorithm Design Techniques
    Greedy Algorithms in Java
  44. Dynamic Programming in Java
  45. Divide and Conquer in Java
  46. Backtracking in Java
  47. Randomized Algorithms in Java
  48. Conclusion
    Recap of DSA in Java

Participants 482

Show more

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:

  1. Create a max-heap from the array of elements.
  2. Select the root node of the max-heap, which is the highest value in the array.
  3. Swap the root node with the last element in the array.
  4. Reduce the size of the heap by one.
  5. 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?

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).

What is the space complexity of Heapsort?

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).

Write a Java program to create a max-heap from an array of elements.

public class Heap 
{ 
    public void buildMaxHeap(int arr[]) 
    { 
        int n = arr.length; 
  
        // Build heap (rearrange array) 
        for (int i = n / 2 - 1; i >= 0; i--) 
            heapify(arr, n, i); 
    } 
  
    // 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; 
  
        Heap ob = new Heap(); 
        ob.buildMaxHeap(arr); 
  
        System.out.println("Max Heap is"); 
        printArray(arr); 
    } 
}

Write a Java program to swap the root node of a max-heap with the last element in the array.

public class Heap 
{ 
    // To swap the root node of a max-heap with the last element in the array 
    public void swapRootNode(int arr[], int n) 
    { 
        int temp = arr[0]; 
        arr[0] = arr[n-1]; 
        arr[n-1] = temp; 
    } 
  
    /* 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; 
  
        Heap ob = new Heap(); 
        ob.swapRootNode(arr, n); 
  
        System.out.println("Array after swapping root node is"); 
        printArray(arr); 
    } 
}