1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #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) {
// WARNING: Not done, yet. Has a bug and a limitation.
// 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;
}
}
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 };
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: */
|
© Copyright 2023 Alexander J. Quinn This content is protected and may not be shared, uploaded, or distributed.