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 78 79 | #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) {
// Find index of max(root, left, right). Suppose the max is the root.
size_t idx_of_max = idx_of_root;
// Could left be the max?
size_t idx_of_left = 2 * idx_of_root + 1;
if(idx_of_left < num_numbers && numbers[idx_of_left] > numbers[idx_of_max]) {
idx_of_max = idx_of_left; // Yes, left is the max (so far).
}
// Could right be the max?
size_t idx_of_right = 2 * idx_of_root + 2;
if(idx_of_right < num_numbers && numbers[idx_of_right] > numbers[idx_of_max]) {
idx_of_max = idx_of_right; // Yes, right is the max.
}
if(idx_of_max != idx_of_root) {
// Swap root value with child value.
int max_value = numbers[idx_of_max];
numbers[idx_of_max] = numbers[idx_of_root]; // move root value to child
numbers[idx_of_root] = max_value; // move child's former value to root
heapify(numbers, num_numbers, idx_of_max); // no longer the max value!
}
}
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_numbers(int const* 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) {
make_heap(numbers, num_numbers);
size_t heap_size = num_numbers;
while(heap_size >= 1) {
// Swap first and last values
int max_value = numbers[0];
numbers[0] = numbers[heap_size - 1];
numbers[heap_size - 1] = max_value;
// Shrink the heap so that the max value is in array but not part of the heap.
heap_size -= 1;
// Heapify, to get the new max into the root (and move the old last to its new home)
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 ▒▒ ▒▒[] = …; array
print_numbers(numbers, num_numbers, "Before heapify: ");
make_heap(numbers, num_numbers);
print_numbers(numbers, num_numbers, "After heapify: ");
heap_sort(numbers, num_numbers);
print_numbers(numbers, num_numbers, "After heap sort: ");
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.