#### Heap Sort 2

D
```/**
* @file
* @author [Dhruv Pasricha](https://github.com/DhruvPasricha)
* @brief [Heap Sort](https://en.wikipedia.org/wiki/Heapsort) implementation
* @details
* Heap-sort is a comparison-based sorting algorithm.
* Heap-sort can be thought of as an improved selection sort:
* like selection sort, heap sort divides its input into a sorted
* and an unsorted region, and it iteratively shrinks the unsorted
* region by extracting the largest element from it and inserting
* it into the sorted region.
*
* Unlike selection sort,
* heap sort does not waste time with a linear-time scan of the
* unsorted region; rather, heap sort maintains the unsorted region
* in a heap data structure to more quickly find the largest element
* in each step.
* Time Complexity : O(Nlog(N))
*/

#include <assert.h>   /// for assert
#include <stdio.h>    /// for IO operations
#include <stdlib.h>   /// for dynamic memory allocation
#include <time.h>     /// for random numbers generation
#include <inttypes.h> /// for uint8_t, int8_t

/**
* @brief Swapped two numbers using pointer
* @param first pointer of first number
* @param second pointer of second number
*/
void swap(int8_t *first, int8_t *second)
{
int8_t temp = *first;
*first = *second;
*second = temp;
}

/**
* @brief heapifyDown Adjusts new root to the correct position in the heap
* This heapify procedure can be thought of as building a heap from
* the top down by successively shifting downward to establish the
* heap property.
* @param arr array to be sorted
* @param size size of array
* @return void
*/
void heapifyDown(int8_t *arr, const uint8_t size)
{
uint8_t i = 0;

while (2 * i + 1 < size)
{
uint8_t maxChild = 2 * i + 1;

if (2 * i + 2 < size && arr[2 * i + 2] > arr[maxChild])
{
maxChild = 2 * i + 2;
}

if (arr[maxChild] > arr[i])
{
swap(&arr[i], &arr[maxChild]);
i = maxChild;
}
else
{
break;
}
}
}

/**
* @brief heapifyUp Adjusts arr[i] to the correct position in the heap
* This heapify procedure can be thought of as building a heap from
* the bottom up by successively shifting upward to establish the
* heap property.
* @param arr array to be sorted
* @param i index of the pushed element
* @return void
*/
void heapifyUp(int8_t *arr, uint8_t i)
{
while (i > 0 && arr[(i - 1) / 2] < arr[i])
{
swap(&arr[(i - 1) / 2], &arr[i]);
i = (i - 1) / 2;
}
}

/**
* @brief Heap Sort algorithm
* @param arr array to be sorted
* @param size size of the array
* @returns void
*/
void heapSort(int8_t *arr, const uint8_t size)
{
if (size <= 1)
{
return;
}

for (uint8_t i = 0; i < size; i++)
{
// Pushing `arr[i]` to the heap

/*heapifyUp Adjusts arr[i] to the correct position in the heap*/
heapifyUp(arr, i);
}

for (uint8_t i = size - 1; i >= 1; i--)
{
// Moving current root to the end
swap(&arr, &arr[i]);

// `heapifyDown` adjusts new root to the correct position in the heap
heapifyDown(arr, i);

}
}

/**
* @brief Self-test implementations
* @returns void
*/
static void test()
{
const uint8_t size = 10;
int8_t *arr = (int8_t *)calloc(size, sizeof(int8_t));

/* generate size random numbers from 0 to 100 */
for (uint8_t i = 0; i < size; i++)
{
arr[i] = rand() % 100;
}
heapSort(arr, size);
for (uint8_t i = 0; i < size - 1; ++i)
{
assert(arr[i] <= arr[i + 1]);
}
free(arr);
}

/**
* @brief Main function
* @returns 0 on exit
*/
int main()
{
// Intializes random number generator
srand(time(NULL));

test(); // run self-test implementations
return 0;
}
```  