Implementation (Part 1)

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

We will build Heap Sort from its core operation up.

Challenge

Easy

The heart of Heap Sort is the sift-down operation. Let's build that first.

Write a function named siftDown that takes an array arr (treated as a binary heap) and an index i, and restores the max-heap property at that node by pushing it down. Compare the node with its two children at 2*i + 1 and 2*i + 2; if the larger child is bigger, swap with it and continue from the child's position. Return the array.

For example, siftDown([1, 10, 5, 3, 2], 0) returns [10, 3, 5, 1, 2].

Try it yourself

#include <stdlib.h>

int* siftDown(int* arr, int arr_size, int i, 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 CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2