Heap Sort Algorithm | Heapify | GeeksforGeeks Beginner's DSA Sheet | Heap Tree

#geeksforgeeks #algorithms #challenge #datastructures

hola coders!

In this video, I solve a Heap Sort problem from GeeksforGee. If you’ve ever struggled with Heap Sort, this is the perfect hands-on example to help you understand how it works in real coding scenarios.

what’s in this video?

Quick explanation of Heap Sort & Heapify
Live problem-solving from GeeksforGeeks
Writing clean & efficient code
Analyzing time complexity

Problem Link: https://www.geeksforgeeks.org/problems/heap-sort/1
Solution Link: https://github.com/debeshp6/Gfg-Tutorials

Code

class Solution {
    // Function to sort an array using Heap Sort.
    public void heapSort(int arr[]) {
        // code here
        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 temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr,i,0);
        }
    }

    public void 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(right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        if(largest != i) {
            int temp = arr[largest];
            arr[largest] = arr[i];
            arr[i] = temp;

            heapify(arr, n, largest);
        }
    }
}

Time Complexity: O(nlogn)

if you're preparing for coding interviews or competitive programming, Heap Sort is a must-know algorithm, and this problem will strengthen your grasp on it!