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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #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_max]) {
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"));
}
}
void heap_sort(int* numbers, size_t num_numbers) {
size_t heap_size = num_numbers;
while(heap_size >= 1) {
// Swap last and root.
int max_value = numbers[0];
numbers[0] = numbers[heap_size - 1];
numbers[heap_size - 1] = max_value;
// Shrink the heap (conceptually)
heap_size -= 1;
// Heapify to merge the new root with the two subheaps.
heapify(numbers, heap_size, 0);
}
}
int main(int argc, char* argv[]) {
int numbers[] = { 5, 7, 2, 1, 3, 4, 9, 8, 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: ");
make_heap(numbers, num_numbers);
print_array(numbers, num_numbers, "AFTER: ");
heap_sort(numbers, num_numbers);
print_array(numbers, num_numbers, "SORTED: ");
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.