Implementation (Part 2)

Lesson 6 of 9 in Coddy's Heap Sort - DSA Series course.

Now we combine building the heap and repeatedly extracting the max.

Challenge

Medium

Now put it all together into the full algorithm.

Write a function named heapSort that takes an integer array and returns it sorted in ascending order.

First build a max-heap by sifting down every non-leaf node, from index n/2 - 1 down to 0. Then repeatedly swap the root (the largest value) with the last element of the heap, shrink the heap by one, and sift the new root back down.

Use a sift-down helper that takes the current heap size, so you can shrink the heap as you go.

Try it yourself

#include <stdlib.h>

int* heapSort(int* arr, int arr_size, int* returnSize) {
    // Write code here
    *returnSize = arr_size;
    return arr;
}

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

All lessons in Heap Sort - DSA Series

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) Project lesson

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2