Bootcamps
Masterclasses
Menu
Courses
Account
Login / Sign Up

Heap Sort

Medium Acceptance 53.06% Points 30

Given an array arr[]. The task is to sort the array elements by Heap Sort.

Examples
Example 1

Example 1

Input: arr[] = [3, 5, 1, 10, 2, 7]

Output: [1, 2, 3, 5, 7, 10]

Explanation: Heap sort is applied to the array by first constructing a max heap. Then, the root element (maximum value) is swapped with the last element in the heap and the heap size is reduced. The process continues until all elements are sorted. The sorted array is [1, 2, 3, 5, 7, 10].

Example 2

Example 2

Input: arr[] = [10, 20, 5, 6, 1, 8]

Output: [1, 5, 6, 8, 10, 20]

Explanation: After applying heap sort to the array, the elements are rearranged in ascending order. The heap sort process involves building a max heap and then performing swaps, followed by reducing the heap size. The final sorted array is [1, 5, 6, 8, 10, 20].

Constraints
  • 1 <= arr.size() <= 10^6
  • 1 <= arr[i] <= 10^6
Hints
  • Expected Time Complexity: O(n log n)
  • Expected Auxiliary Space: O(1)
Topics
Heap
Companies
Amazon Microsoft Samsung Visa Oracle
Added 11 Apr 2025 53.06% acceptance
Ln 1, Col 1Sign in to save your code
3 5 1 10 2 7
1 2 3 5 7 10