Things To Remember in Heap Sort

By the end of this article, you will have the answers to these questions

1. Why should I learn Heap sort

2. what should I remember in the context of CP

WHY?

• The major advantage of heap sort is, we can sort the given array in place

• so space complexity becomes O(1)

By now, I hope you have received an answer explaining the reasons behind the importance of learning about heap sort.

Heap Sort Code

public class HeapsortDemo{  
    public static void sort(int arr[]){
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) // Building heap from given  random array
            heapify(arr, n, i);
        for (int i = n - 1; i >= 0; i--) { // sorting the elements one by one
            // i starts from last index .
            // swap elements at index i , 0 .
            // heapify the array till i . 
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

 public void static 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 left child is larger than root.
        if (right < n && arr[right] > arr[largest])  largest = right; // If right child is larger than largest so far
        if (largest != i) {         // largest changes only when array does not satisfy max heap order property.
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }
 public 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 args[])
    {
        int arr[] = { 2, 1, 3, 19, 16, 18 };
        int N = arr.length;
        sort(arr);
        System.out.println("Sorted array is");
        printArray(arr);
    }
}

output :- 
Sorted array is
[1,2,3,16,18,19]

Try To Code

Is there an alternative way to use heap sort without having to implement the code from scratch every time it is needed?

Yes, you can use Priority Queues

// Min Heap
PriorityQueues<E> heap = new PriorityQueues<E>();

// Max Heap 
PriorityQueues<E> heap = new PriorityQueues<E>(Collections.reverseOrder());

Methods:-

1. add(obj)

2. peek()

3. remove() -> removes and returns the element

What should I remember in the context of CP?

Arrays.sort(array_name);  // for arrays
Collections.sort(array_name) // for collections 
// ********* and It is good to remember the heap sort procedure , helps in problem with high space constraints

Mostly you will find the problem in the heap concept, but here are a few problems sorry one of the problems related to heap sort

kth-smallest-element

Thank you for investing your time in reading this article. I sincerely hope it has provided valuable insights to enhance your journey. If you found it helpful, I encourage you to consider subscribing for more informative content. Feel free to share your insights or any additional information that could contribute to the discussion.

Happy Coding.