#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

void heapify(int* numbers, size_t num_numbers, size_t idx_of_root) {
    // Goal:  Find the idx of max among root, left, and right.
    size_t idx_of_max = idx_of_root;

    size_t idx_of_left  = 2* idx_of_root + 1;
    // Is the left the max?
    if(idx_of_left < num_numbers && numbers[idx_of_left] > numbers[idx_of_root]) {
        idx_of_max = idx_of_left;
    }

    size_t idx_of_right = 2* idx_of_root + 2;
    // Is the right the max?
    if(idx_of_right < num_numbers && numbers[idx_of_right] > numbers[idx_of_root]) {
        idx_of_max = idx_of_right;
    }

    if(idx_of_max != idx_of_root) {
        // Swap the child value with root value.
        int max_value = numbers[idx_of_max];
        numbers[idx_of_max] = numbers[idx_of_root];
        numbers[idx_of_root] = max_value;

        heapify(numbers, num_numbers, idx_of_max);  // no longer the max!
    }
}

void make_heap(int* numbers, size_t num_numbers) {
    size_t idx_of_last = num_numbers - 1;
    size_t idx_of_last_parent = (idx_of_last - 1) / 2;
    for(int i = idx_of_last_parent; i >= 0; i--) {
        heapify(numbers, num_numbers, i);
    }
}

void print_array(int* numbers, size_t num_numbers, char const* prefix) {
    printf("%s", prefix);
    for(int i = 0; i < num_numbers; i++) {
        printf("[%d]%s", numbers[i], (i + 1 < num_numbers ? "→" : "\n"));
    }
}

int main(int argc, char* argv[]) {
    int numbers[] = { 5, 7, 2, 1, 3, 4, 9, 2, 0, 6 };
    //int numbers[] = { 1, 2, 5 };
    size_t num_numbers = sizeof numbers / sizeof numbers[0]; // only for ▒▒ ▒▒[] = …; arrays
    print_array(numbers, num_numbers, "BEFORE: ");
    heapify(numbers, num_numbers, 0);
    print_array(numbers, num_numbers, "AFTER:  ");
    
    return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */