Heap Sort

Pre-requisites: Implement Max-Heap, Build max-heap from an array

Intuition:

The aim is to sort an array in ascending order. A straightforward method is to repeatedly pick out the largest element from the unsorted part of the array and place it at the end. Once the largest element is in its correct spot, the algorithm only needs to focus on the remaining (now smaller) unsorted portion.

To efficiently get the largest element in constant time, the array can be organized into a Max Heap. A Max Heap is a special kind of binary tree where every parent node is greater than or equal to its children. In array form, the biggest element always ends up at index 0 (the root of the heap).

Why a Max-heap?

With a Max Heap, the largest element is immediately available at index 0 without extra searching. This makes it easy to place the largest element at the end of the array. If the goal is to sort the array in descending order, the minimum element must be picked every time, which requires building a Min Heap instead.

Approach:

Rearrange the elements of the array and build a max-heap.
Start iterating with the whole array being unsorted initially.
Swap the element at index 0 (the largest) with the element at the last position in the unsorted portion of the array. The largest element is now at the end, in its correct sorted position.
Reduce the size of unsorted portion of the array by one from the back (since the very last element is now sorted).
Re-heapify from the top (index 0) downwards to restore the Max Heap property for the remaining unsorted portion (the sorted portion of the array must be kept undisturbed).

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Function to recursively heapify the array downwards
    void heapifyDown(vector<int> &arr, int last, int ind) {
        // Index of largest element
        int largestInd = ind; 

        // Indices of the left and right children
        int leftChildInd = 2*ind + 1, rightChildInd = 2*ind + 2;
        
        // If the left child holds larger value, update the largest index
        if(leftChildInd <= last && arr[leftChildInd] > arr[largestInd]) 
            largestInd = leftChildInd;

        // If the right child holds larger value, update the largest index
        if(rightChildInd <= last && arr[rightChildInd] > arr[largestInd]) 
            largestInd = rightChildInd;

        // If the largest element index is updated
        if(largestInd != ind) {
            // Swap the largest element with the current index
            swap(arr[largestInd] , arr[ind]);

            // Recursively heapify the lower subtree
            heapifyDown(arr, last, largestInd);
        }
        return; 
    }

    // Function to build Max-heap from the given array
    void buildMaxHeap(vector<int> &nums) {
        int n = nums.size();
        
        // Iterate backwards on the non-leaf nodes
        for(int i = n/2 - 1; i >= 0; i--) {
            // Heapify each node downwards
            heapifyDown(nums, n-1, i);
        }
        return;
    }

public:
    // Function to sort the array using heap-sort
    void heapSort(vector<int> &nums) {
        
        // Function call to build a max-heap from the given array
        buildMaxHeap(nums);
        
        // To store the last Index
        int last = nums.size() - 1; 
        
        // Until there are elements left to sort in the array
        while(last > 0) {
            // Swap the greatest element to the current last index
            swap(nums[0], nums[last]);
            last--; // Decrement the last index
            
            if(last > 0) {
                // Heapify down the root
                heapifyDown(nums, last, 0);
            }
        }
        
        return;
    }
};

// Driver code
int main() {
    vector<int> nums = {60, 30, 40, 20, 10, 50};
    
    cout << "Input Array: ";
    for(int x : nums) cout << x << " ";
    
    // Creating an object of Solution class
    Solution sol;
    
    // Function call to sort the array using heap-sort
    sol.heapSort(nums);
    
    cout << "\nSorted Array: ";
    for(int x : nums) cout << x << " ";
    
    return 0;
}
class Solution {
    // Function to recursively heapify the array downwards
    private void heapifyDown(int[] arr, int last, int ind) {
        // Index of largest element
        int largestInd = ind; 

        // Indices of the left and right children
        int leftChildInd = 2 * ind + 1, rightChildInd = 2 * ind + 2;
        
        // If the left child holds larger value, update the largest index
        if(leftChildInd <= last && arr[leftChildInd] > arr[largestInd]) {
            largestInd = leftChildInd;
        }

        // If the right child holds larger value, update the largest index
        if(rightChildInd <= last && arr[rightChildInd] > arr[largestInd]) {
            largestInd = rightChildInd;
        }

        // If the largest element index is updated
        if(largestInd != ind) {
            // Swap the largest element with the current index
            int temp = arr[largestInd];
            arr[largestInd] = arr[ind];
            arr[ind] = temp;

            // Recursively heapify the lower subtree
            heapifyDown(arr, last, largestInd);
        }
        return; 
    }

    // Function to build Max-heap from the given array
    private void buildMaxHeap(int[] nums) {
        int n = nums.length;
        
        // Iterate backwards on the non-leaf nodes
        for(int i = n / 2 - 1; i >= 0; i--) {
            // Heapify each node downwards
            heapifyDown(nums, n - 1, i);
        }
        return;
    }

    // Function to sort the array using heap-sort
    public void heapSort(int[] nums) {
        
        // Function call to build a max-heap from the given array
        buildMaxHeap(nums);
        
        // To store the last Index
        int last = nums.length - 1; 
        
        // Until there are elements left to sort in the array
        while(last > 0) {
            // Swap the greatest element to the current last index
            int temp = nums[0];
            nums[0] = nums[last];
            nums[last] = temp;

            last--; // Decrement the last index
            
            if(last > 0) {
                // Heapify down the root
                heapifyDown(nums, last, 0);
            }
        }
        
        return;
    }
}

// Driver code in a separate Main class
class Main {
    public static void main(String[] args) {
        int[] nums = {60, 30, 40, 20, 10, 50};
        
        System.out.print("Input Array: ");
        for(int x : nums) {
            System.out.print(x + " ");
        }
        
        // Creating an object of Solution class
        Solution sol = new Solution();
        
        // Function call to sort the array using heap-sort
        sol.heapSort(nums);
        
        System.out.print("\nSorted Array: ");
        for(int x : nums) {
            System.out.print(x + " ");
        }
    }
}
# Function to recursively heapify the array downwards
class Solution:
    def heapifyDown(self, arr, last, ind):
        # Index of largest element
        largestInd = ind

        # Indices of the left and right children
        leftChildInd = 2 * ind + 1
        rightChildInd = 2 * ind + 2
        
        # If the left child holds larger value, update the largest index
        if leftChildInd <= last and arr[leftChildInd] > arr[largestInd]:
            largestInd = leftChildInd

        # If the right child holds larger value, update the largest index
        if rightChildInd <= last and arr[rightChildInd] > arr[largestInd]:
            largestInd = rightChildInd

        # If the largest element index is updated
        if largestInd != ind:
            # Swap the largest element with the current index
            arr[largestInd], arr[ind] = arr[ind], arr[largestInd]

            # Recursively heapify the lower subtree
            self.heapifyDown(arr, last, largestInd)
        return

    # Function to build Max-heap from the given array
    def buildMaxHeap(self, nums):
        n = len(nums)
        
        # Iterate backwards on the non-leaf nodes
        for i in range(n // 2 - 1, -1, -1):
            # Heapify each node downwards
            self.heapifyDown(nums, n - 1, i)
        return

    # Function to sort the array using heap-sort
    def heapSort(self, nums):
        # Function call to build a max-heap from the given array
        self.buildMaxHeap(nums)
        
        # To store the last Index
        last = len(nums) - 1
        
        # Until there are elements left to sort in the array
        while last > 0:
            # Swap the greatest element to the current last index
            nums[0], nums[last] = nums[last], nums[0]
            last -= 1  # Decrement the last index
            
            if last > 0:
                # Heapify down the root
                self.heapifyDown(nums, last, 0)
        
        return

# Driver code
if __name__ == "__main__":
    nums = [60, 30, 40, 20, 10, 50]
    
    print("Input Array:", end=" ")
    for x in nums:
        print(x, end=" ")
    
    # Creating an object of Solution class
    sol = Solution()
    
    # Function call to sort the array using heap-sort
    sol.heapSort(nums)
    
    print("\nSorted Array:", end=" ")
    for x in nums:
        print(x, end=" ")
// Function to recursively heapify the array downwards
class Solution {
    heapifyDown(arr, last, ind) {
        // Index of largest element
        let largestInd = ind; 

        // Indices of the left and right children
        let leftChildInd = 2 * ind + 1;
        let rightChildInd = 2 * ind + 2;
        
        // If the left child holds larger value, update the largest index
        if (leftChildInd <= last && arr[leftChildInd] > arr[largestInd]) {
            largestInd = leftChildInd;
        }

        // If the right child holds larger value, update the largest index
        if (rightChildInd <= last && arr[rightChildInd] > arr[largestInd]) {
            largestInd = rightChildInd;
        }

        // If the largest element index is updated
        if (largestInd !== ind) {
            // Swap the largest element with the current index
            [arr[largestInd], arr[ind]] = [arr[ind], arr[largestInd]];

            // Recursively heapify the lower subtree
            this.heapifyDown(arr, last, largestInd);
        }
        return; 
    }

    // Function to build Max-heap from the given array
    buildMaxHeap(nums) {
        let n = nums.length;
        
        // Iterate backwards on the non-leaf nodes
        for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
            // Heapify each node downwards
            this.heapifyDown(nums, n - 1, i);
        }
        return;
    }

    // Function to sort the array using heap-sort
    heapSort(nums) {
        // Function call to build a max-heap from the given array
        this.buildMaxHeap(nums);
        
        // To store the last Index
        let last = nums.length - 1; 
        
        // Until there are elements left to sort in the array
        while (last > 0) {
            // Swap the greatest element to the current last index
            [nums[0], nums[last]] = [nums[last], nums[0]];
            last--; // Decrement the last index
            
            if (last > 0) {
                // Heapify down the root
                this.heapifyDown(nums, last, 0);
            }
        }
        
        return;
    }
}

// Driver code
(function() {
    let nums = [60, 30, 40, 20, 10, 50];
    
    console.log("Input Array:", ...nums);
    
    // Creating an object of Solution class
    let sol = new Solution();
    
    // Function call to sort the array using heap-sort
    sol.heapSort(nums);
    
    console.log("Sorted Array:", ...nums);
})();

Complexity Analysis:

Time Complexity: O(N*logN), where N is the size of the array
Building a max-heap from the array takes O(N) iterations. Once done, each node is placed at its correct index and the array is heapified (which takes logN iterations) taking overall O(N*logN) time.

Space Complexity: O(logN)
Recursive stack space used while building the max-heap is O(logN). Also, the depth of each heapify Down will take O(logN) space.

Note:

Although heapifyDown() may be invoked multiple times (up to N calls in total), each call finishes before the next one begins. Hence, the recursive calls do not stack on top of each other, ensuring that the maximum stack depth remains O(log N) at any point in time. As a result, the overall auxiliary space complexity (due to recursion) is O(log N).

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Why a Max-heap?

Approach:

Solution:

Complexity Analysis:

Note:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code