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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
// This version was modified on 11/1/2023 (after both lectures).
void swap(int* a_n1, int* a_n2) {
int n1_orig = *a_n1;
*a_n1 = *a_n2;
*a_n2 = n1_orig;
}
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(&numbers[idx_of_max], &numbers[idx_of_root]); // Swap root value with child value.
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(size_t i = idx_of_last_parent + 1; i-- > 0; ) { // count idx_of_last_parent to 0 (inclusive)
heapify(numbers, num_numbers, i);
}
}
void delete_root(int* numbers, size_t* a_num_numbers) {
numbers[0] = numbers[(*a_num_numbers) - 1];
*a_num_numbers -= 1;
heapify(numbers, *a_num_numbers, 0);
}
void insert(int* numbers, size_t* a_num_numbers, int new_number) {
// Write the new value to end of heap (assuming memory already allocated).
*a_num_numbers += 1;
size_t idx_of_new = (*a_num_numbers) - 1;
numbers[idx_of_new] = new_number;
// Bubble the new value up in the tree.
size_t idx_of_parent = (idx_of_new - 1) / 2;
while(idx_of_new > 0 && new_number > numbers[idx_of_parent]) {
swap(&numbers[idx_of_new], &numbers[idx_of_parent]);
idx_of_new = idx_of_parent;
idx_of_parent = (idx_of_new - 1) / 2;
}
}
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
swap(&numbers[0], &numbers[heap_size - 1]);
// 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[20] = { 5, 7, 2, 1, 3, 4, 9, 8, 0, 6 };
//int numbers[] = { 1, 2, 5 };
size_t capacity = sizeof numbers / sizeof numbers[0]; // only for ▒▒ ▒▒[] = …; array
size_t num_numbers = 10;
print_numbers(numbers, num_numbers, "Before heapify: ");
make_heap(numbers, num_numbers);
print_numbers(numbers, num_numbers, "After heapify: ");
insert(numbers, &num_numbers, 55);
print_numbers(numbers, num_numbers, "After ins 55: ");
insert(numbers, &num_numbers, 1);
print_numbers(numbers, num_numbers, "After ins 1: ");
delete_root(numbers, &num_numbers);
print_numbers(numbers, num_numbers, "After pop: ");
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.