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.
2

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

void heapify(int arr, int n, int i) {
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2i + 1
int r = 2 * i + 2; // right = 2i + 2

// If left child is larger than root
if (l < n && arr[l] > arr[largest])
    largest = l;

// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
    largest = r;

// If largest is not root
if (largest != i) {
    swap(arr[i], arr[largest]);

    // Recursively heapify the affected sub-tree
    heapify(arr, n, largest);
}

}

// main function to do heap sort
void heapSort(int arr, int n) {
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i–)
heapify(arr, n, i);

// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
    // Move current root to end
    swap(arr[0], arr[i]);

    // call max heapify on the reduced heap
    heapify(arr, i, 0);
}

}

int main() {
int n;
cin >> n;

int arr[n];
for (int i = 0; i < n; i++) {
    cin >> arr[i];
}

heapSort(arr, n);

for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
}

return 0;

}

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

  1. Building a Max-Heap:
  • Start from the last non-leaf node.
  • For each node, ensure its children are smaller or equal.
  • Recursively heapify the subtree rooted at the node.
  1. Extracting Elements:
  • Swap the root (largest element) with the last element.
  • Reduce the heap size by one.
  • Heapify the root to maintain the max-heap property.
  • Repeat until the heap is empty.

Time Complexity: O(n log n) Space Complexity: O(1) (in-place)