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.