binary_heap.c

#include <stdio.h>
#include <stdlib.h>
#define MIN_HEAP_SIZE 16
#define DEFAULT_VALUE -1000

int* initialize_min_heap();
void insert(int* min_heap, int num);
void visualize_min_heap(int* min_heap);
void print_min_heap(int* min_heap);
void delete_min(int* min_heap);

const int initial_space[] = {12, 6, 2, 0};
const int space_between[] = {0, 10, 4, 1};
const int startIndex[] = {1, 2, 4, 8};
const int endIndex[] = {1, 3, 7, 15};

int main() {
    int* min_heap = initialize_min_heap();
    int i;
    
    // Please enter 2 digit numbers. visualize function messes up with numbers that contain greater than 2 digits
    while (1) {
        int command;
        printf("Enter command:\n");
        printf("1: Insert, 2: Delete the root, 0: Exit: ");
        scanf("%d", &command);
        if (command == 0) {
            break;
        }
        
        switch(command) {
            case 1:
                printf("Number: ");
                int num;
                scanf("%d", &num);
                insert(min_heap, num);
                break;
            case 2:
                delete_min(min_heap);
                break;
        }
        visualize_min_heap(min_heap);
        printf("\n");
    }
    
    free(min_heap);
}

int* initialize_min_heap() {
    int* min_heap = malloc(sizeof(int) * MIN_HEAP_SIZE);
    int i;
    for (i = 1; i < MIN_HEAP_SIZE; i++) {
        min_heap[i] = DEFAULT_VALUE;
    }
    return min_heap;
}

void insert(int* min_heap, int num) {
    int index = 1;
    // Insert
    while (index < MIN_HEAP_SIZE) {
        if (min_heap[index] == DEFAULT_VALUE) {
            min_heap[index] = num;
            break;
        }
        index++;
    }
    // Check if children is greater than parents elements
    while (index / 2 != 0) {
        int parentNum = min_heap[index / 2];
        if (parentNum > min_heap[index]) {
            min_heap[index / 2] = min_heap[index];
            min_heap[index] = parentNum;
        }
        index /= 2;
    }
}

void delete_min(int* min_heap) {
    int index = MIN_HEAP_SIZE - 1;
    
    // Get the index that goes to index 1
    while (index > 0) {
        if (min_heap[index] != DEFAULT_VALUE) {
            break;
        }
        index--;
    }
    int num_elements = index;
    min_heap[1] = min_heap[index];
    min_heap[index] = DEFAULT_VALUE;
    
    index = 1;
    while (index * 2 + 1 < MIN_HEAP_SIZE) {
        if (min_heap[2 * index] != DEFAULT_VALUE && min_heap[2 * index + 1] != DEFAULT_VALUE && (min_heap[index] > min_heap[2 * index] || min_heap[index] > min_heap[2 * index + 1])) {
            if (min_heap[2 * index] < min_heap[2 * index + 1]) {
                int temp = min_heap[index];
                min_heap[index] = min_heap[2 * index];
                min_heap[2 * index] = temp;
                index = 2 * index;
            } else {
                int temp = min_heap[index];
                min_heap[index] = min_heap[index * 2 + 1];
                min_heap[2 * index + 1] = temp;
                index = 2 * index + 1;
            }
        } else {
            break;
        }
    }
}

void print_min_heap(int* min_heap) {
    int i;
    for (i = 1; i < MIN_HEAP_SIZE; i++) {
        if (min_heap[i] == DEFAULT_VALUE) {
            break;
        }
        printf("%d ", min_heap[i]);
    }
    printf("\n");
}

void visualize_min_heap(int* min_heap) {
    int layer = 0;
    int index, i;
    for (index = 1; index < MIN_HEAP_SIZE; index++) {
        // Print leading spaces
        if (index == startIndex[layer]) {
            for (i = 0; i < initial_space[layer]; i++) {
                printf(" ");
            }
        }
        // If the value is set, print that
        if (min_heap[index] != DEFAULT_VALUE) {
            printf("%d", min_heap[index]);
        }
        // Prints out the space between numbers
        for (i = 0; i < space_between[layer]; i++) {
            printf(" ");
        }
        // If that is the end of that layer, go to the next line
        if (index == endIndex[layer]) {
            printf("\n");
            layer++;
        }
    }
}