#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>

	#define MAX_NAME_LEN 10 // 9 chars + 1 null terminator

	typedef struct Student {
		int ID;
		char name[MAX_NAME_LEN];
	} Student;

	typedef struct Heap {
		Student **students;
		int capacity;
		int size;
	} Heap;

	// Function prototypes
	Student *initStudent(char *name, int ID);
	Heap *initHeap(Student **students, int size);
	Heap *heapify(Student **students, int size);
	void percolateDown(Student **students, int size, int idx);
	void percolateUp(Student **students, int idx);
	void swap(Student **stud1, Student **stud2);
	int doubleCapacity(Heap *heap);
	void insert(Heap *heap, Student *newStudent);
	Student *removeMin(Heap *heap);
	void printStudents(Student **students, int size);
	void freeHeap(Heap *heap);

	// Initializes and returns new student
	Student *initStudent(char *name, int ID) {
		Student *student = malloc(sizeof(Student));
		strcpy(student->name, name);
		student->ID = ID;
		return student;
	}

	// Helper function for Heapify
	// Takes in heap formatted array and heap data and returns initialized heap
	Heap *initHeap(Student **students, int size) {
		Heap *heap = malloc(sizeof(Heap));
		heap->size = size;
		Student **temp = realloc(students, sizeof(Student *) * (2 * size + 1));
		heap->capacity = size;
		if (temp) {
			students = temp;
			heap->capacity *= 2;
		}
		heap->students = students;
		return heap;
	}

	// Takes an existing array of students and converts/ returns heap
	// Initializes heap->capacity with current size * 2 if realloc is successful
	// Assumes existing array holds garbage value at 0 (1-based array / heap)
	Heap *heapify(Student **students, int size) {
		if (!students)
			return NULL;

		for (int i = size / 2; i > 0; i--) {
			percolateDown(students, size, i);
		}

		return initHeap(students, size);
	}

	// Keeps swapping nodes downwards to enforce min-heap constraints
	// Finds child with smallest ID, swaps if that childs ID is less than ID at
	// current node Recursively calls downwards after swap
	void percolateDown(Student **students, int size, int idx) {
		if (idx > size)
			return;

		if (idx * 2 + 1 <= size) {
			int smallerIDIdx = (students[idx * 2]->ID < students[idx * 2 + 1]->ID)
														 ? (idx * 2)
														 : (idx * 2 + 1);
			if (students[smallerIDIdx]->ID < students[idx]->ID) {
				swap(students + idx, students + smallerIDIdx);
				percolateDown(students, size, smallerIDIdx);
			}

		} else if ((idx * 2 <= size)) {
			if (students[idx * 2]->ID < students[idx]->ID) {
				swap(students + idx, students + idx * 2);
				percolateDown(students, size, idx * 2);
			}
		}
	}

	// Keeps swapping nodes upwards to enforce min-heap constraints
	// swaps if ID at current node is less than the parent node's ID
	// Recursively calls upwards after swap
	void percolateUp(Student **students, int idx) {
		if (idx / 2 <= 0)
			return;

		if (students[idx]->ID < students[idx / 2]->ID) {
			swap(students + idx, students + (idx / 2));
			percolateUp(students, (idx / 2));
		}
	}

	// Swap two students in Student pointer array
	void swap(Student **stud1, Student **stud2) {
		Student *temp = *stud1;
		*stud1 = *stud2;
		*stud2 = temp;
	}

	// Attempts to double capacity of heap
	// Updates heap->capacity if successful and returns 1
	// Returns 0 if realloc fails
	int doubleCapacity(Heap *heap) {
		Student **temp =
				realloc(heap->students, sizeof(Student *) * (heap->capacity * 2 + 1));
		if (!temp)
			return 0;
		heap->students = temp;
		heap->capacity *= 2;
		return 1;
	}

	// Resizes heap->students if heap is full
	// Increments heap->size
	// Adds student to end next available array index
	// NOTE: By doing this, heap maintains property of a complete tree
	// Calls percolate up at newly added node
	void insert(Heap *heap, Student *newStudent) {
		if (heap->size == heap->capacity) {
			if (!doubleCapacity(heap)) {
				printf("\nFailed to add student to heap.\n");
				return;
			}
		}
		heap->students[++heap->size] = newStudent;
		percolateUp(heap->students, heap->size);

		printf("\nAdded %s to the heap.\n", newStudent->name);
	}

	// Stores the first student from the first index
	// Moves last student in array to the front
	// Decrement heap->size
	// Call percolate down from the first node in heap
	// Return stored student
	Student *removeMin(Heap *heap) {
		if (heap->size == 0)
			return NULL;
		Student *minStudent = heap->students[1];

		heap->students[1] = heap->students[heap->size];
		heap->students[heap->size] = NULL;
		heap->size--;
		percolateDown(heap->students, heap->size, 1);

		return minStudent;
	}

	// Prints all students in a heap with corresponding index
	void printStudents(Student **students, int size) {
		for (int i = 1; i <= size; i++)
			printf("%2d) %-9s - %-3d\n", i, students[i]->name, students[i]->ID);
		printf("\n");
	}

	// Frees all memory associated with heap
	void freeHeap(Heap *heap) {
		for (int i = 1; i <= heap->size; i++) {
			free(heap->students[i]);
		}
		free(heap->students);
		free(heap);
	}

	int main() {

		/*
			The following code does the following:
			Creates an array of students with assigned names and IDs
			Creates a min-heap that calls heapify on this array
				NOTE: Purpose of heapify
					Inserting each element of array into an empty heap directly
					would be an O(nlogn). By using heapify on an existing array,
					converting to a heap turns into an O(n) operation.
			Adds a new student is inserted into the heap
			Removes the minimum student from the heap
			Then frees all allocated memory

			Time complexity:
			- heapify   : O(n)
			- insert    : O(logn)
			- removeMin : O(logn)
		*/

		int numStudents = 10;
		Student **students = malloc(sizeof(Student *) * (numStudents + 1));
		students[0] = NULL; // 1-based array | idx 0 is not used
		char *names[] = {"Bobby", "Billy", "Jamie", "Oliver", "Rebecca",
										 "Julia", "Jared", "Ralph", "Hannah", "Natasha"};
		for (int i = 1; i <= numStudents; i++) {
			int ID = rand() % 255 + 1; // Random ID in inclusive range [1,255]
			students[i] = initStudent(names[i - 1], ID);
		}
		printf("STUDENTS BEFORE HEAPIFY:\n");
		printStudents(students, numStudents);

		Heap *heap = heapify(students, numStudents);

		printf("STUDENTS AFTER HEAPIFY:\n");
		printStudents(heap->students, heap->size);

		printf("NOTE:\nHeapify does not sort the array.\n"
					 "It restructures the array with binary min-heap properties.\n"
					 "i.e. Each parent has an ID less than or equal to its children.\n");

		printf("\nTRACE EXAMPLE:\nID at index 1 less than ID at index 2 and 3\n"
					 "ID at index 2 less than ID at index 4 and 5\n"
					 "ID at index 3 less than ID at index 6 and 7\n"
					 "And so on...\nRemember children of index i are found at\n"
					 "indexes (2 * i) and (2 * i + 1)\n");

		printf("\nAttempting to add student:\n"
					 "Name: Johnny\nID: 98\n");

		Student *newStudent = initStudent("Johnny", 98);

		insert(heap, newStudent);

		printf("\nSTUDENTS AFTER ADDING JOHNNY:\n");
		printStudents(heap->students, heap->size);

		printf("\nRemoving student with smallest ID:\n");
		Student *minStudent = removeMin(heap);

		if (!minStudent)
			printf("\nHeap is empty\n");
		else {
			printf("\n%s has been removed from the heap\n", minStudent->name);

			printf("\nSTUDENTS AFTER REMOVING MIN:\n");
			printStudents(heap->students, heap->size);
			free(minStudent);
		}

		freeHeap(heap);

		return 0;
	}