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.