Introduction

Heap Sort is an efficient comparison-based sorting algorithm that uses:

 Binary Heap Data Structure

The idea is:

  1. Build a Max Heap
  2. Place largest element at root
  3. Swap root with last element
  4. Reduce heap size
  5. Heapify again

This problem helps in understanding:

  • heaps
  • heapify process
  • tree-based sorting
  • in-place sorting

Example

Input:arr = [4, 10, 3, 5, 1]

Output:
[1, 3, 4, 5, 10]

Explanation:
Largest elements are repeatedly moved to correct position using Max Heap.

Constraints

 1 <= arr.length <= 10^5-10^9 <= arr[i] <= 10^9

Approach : Max Heap

Explanation

Heap Sort works in two phases:

  1. Build Max Heap
    • largest element moves to root
  2. Sorting Phase
    • swap root with last element
    • reduce heap size
    • heapify again

Heapify ensures:

  • parent node remains larger
    than children

Steps

  1. Build Max Heap.
  2. Swap root with last element.
  3. Reduce heap size.
  4. Heapify root again.
  5. Repeat until array sorted.

Dry Run

Input:[4, 10, 3, 5, 1]

Build Max Heap:
[10, 5, 3, 4, 1]

Swap root and last:
[1, 5, 3, 4, 10]

Heapify:
[5, 4, 3, 1, 10]

Swap root and last:
[1, 4, 3, 5, 10]

Continue process...

Final Result:
[1, 3, 4, 5, 10]

Heap Sort Code

 

Complexity Analysis

Time Complexity: O(n log n) Explanation: Heapify operation runs log n times for every element. 
Space Complexity: O(1) Explanation: Sorting is performed in-place.

Edge Cases

  1. Empty array
  2. Single element array
  3. Already sorted array
  4. Reverse sorted array
  5. Duplicate elements present

Why This Problem is Important

Heap Sort helps in understanding:

  1. Heap Data Structure
  2. Heapify process
  3. Tree-based sorting
  4. In-place sorting
  5. Priority-based ordering

It is one of the most important advanced sorting algorithms.

Real-World Applications

Heap Sort concepts are used in:

  1. Priority queues
  2. Operating systems
  3. Task scheduling
  4. Graph algorithms
  5. Real-time systems

Common Mistakes

  1. Incorrect heapify indices
  2. Wrong child calculations
  3. Forgetting reduced heap size
  4. Incorrect heap building order

Interview Tips

Interviewers often expect:

  1. Heapify explanation
  2. Heap construction understanding
  3. O(n log n) analysis

Always explain:

  • Max Heap property
  • heapify operation
  • sorting phase separately

Related Questions

  1. Count Sort
  2. Quick Sort
  3. Merge Sort
  4. Kth Largest Element
  5. Priority Queue Problems

Final Takeaway

Heap Sort is a fundamental heap-based sorting algorithm that teaches heap construction and priority-based ordering techniques. Understanding Heap Sort builds a strong foundation for advanced heap and sorting interview problems.