HEAPEDU4 - Editorial

editorial
, , ,
1

Problem Link - Heap sort Practice Problem in Heaps

Problem Statement

Given an array of integers, we need to sort it in ascending order using Heap Sort.

Approach

Heap Sort is a comparison-based sorting algorithm that works by:

  1. First, building a max-heap from the array.
  2. Then, repeatedly extracting the largest element from the heap and placing it at the end of the array.

Steps of the Algorithm

  1. Build the Max-Heap:
  • Start from the last non-leaf node and call the heapify function for each node up to the root.
  • The heapify function ensures that the subtree rooted at the current index follows the max-heap property.
  1. Extract Elements One by One:
  • Swap the root of the max-heap (the largest element) with the last element in the heap.
  • Reduce the heap size by one and call heapify on the root to restore the max-heap property.
  • Repeat this process until the heap is reduced to a single element.
  • For heapify see this - Insertion in a Heap Practice Problem in Heaps

Complexity

  • Time Complexity: Building the max-heap takes O(n). Each extraction operation involves a heapify call, which takes O(logn) and is performed n times, leading to O(n log ⁡n) for the sorting phase. Thus, the overall time complexity is O(n log⁡ n).
  • Space Complexity: The space complexity is O(1) for in-place sorting, ignoring the input array space.