I have tried to implement my Heap in C. The following are the 13 operations defined:

- build_maxheap
- insert
- exctract_max (delete heap max root)
- max_delete (delete an element or key)
- max_heapify
- clear 
- heapSort
- get_max
- print
- increase_key (helper function for insert and delete key functions)
- height
- is_empty
- is_maxheap (checks if the array is a heap)

This is the code in C:

```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

typedef struct MaxHeap {
 int size;
 int* heap;
} MaxHeap;

const MaxHeap maxheap_init = { .size = 0, .heap = NULL };
int INF = 1000, N_INF = -1000;

void swap(int* a, int* b) {
 int temp = *a;
 *a = *b;
 *b = temp;
}

int parent(int i) { 
 return (i-1)/2; 
}
 
int left(int i) { 
 return (2*i + 1); 
}
 
int right(int i) { 
 return (2*i + 2);
}

int get_max(MaxHeap* max_heap) { //O(1)
 return max_heap->heap[0];
}

int is_empty(MaxHeap* max_heap) {
 return max_heap->heap[0] == N_INF;
}

int height(MaxHeap* max_heap) {
 return floor(log2(max_heap->size));
}

MaxHeap* create_maxheap(int size) {
 MaxHeap* heap = calloc(size, sizeof * heap);
 if (!heap) return heap;
 heap->size = size;
 return heap;
}

void max_heapify(int* data, int* key_index, int i, int size) { // O(logn)
 int largest = i, leftie = left(i), rightie = right(i);
 
 if (leftie < size && data[leftie] > data[largest])
 largest = leftie;
 if (rightie < size && data[rightie] > data[largest])
 largest = rightie;//transitvity 
 if (largest != i) {
 swap(&data[i], &data[largest]);
 //
 key_index[data[i]] = i;
 key_index[data[largest]] = largest;
 //
 max_heapify(data, key_index, largest, size);
 }
}

void increase_key(MaxHeap* max_heap, int* key_index, int j, int key) {
 if (key < max_heap->heap[j])
 printf("Error: key must be larger \n");
 else {
 max_heap->heap[j] = key;
 key_index[key] = j;
 for (int i = j; i > 0; i = parent(i)) {
 if (max_heap->heap[i] > max_heap->heap[parent(i)]) {
 swap(&max_heap->heap[i], &max_heap->heap[parent(i)]);
 key_index[max_heap->heap[i]] = i;
 key_index[max_heap->heap[parent(i)]] = parent(i);
 }
 else break;
 }
 }
}

int* build_max_heap(int* data, int* key_index, int size) { //O(n)
 for (int i = size / 2 - 1; i >= 0; i--) {
 max_heapify(data, key_index, i, size);
 }
 return data;
}

void max_insert(MaxHeap* max_heap, int* key_index, int key) { // O(logn)
 int* temp = realloc (max_heap->heap, (max_heap->size + 1) * sizeof (*(max_heap->heap)));
 if (temp) {
 max_heap->heap = temp;
 max_heap->heap[max_heap->size] = N_INF;
 increase_key(max_heap, key_index, max_heap->size, key);
 max_heap->size += 1;
 temp = 0;
 }
}

void extract_max(MaxHeap* max_heap, int* key_index) { // O(logn)
 swap(&max_heap->heap[0], &max_heap->heap[max_heap->size - 1]);
 max_heap->size -= 1;
 max_heapify(max_heap->heap, key_index, 0, max_heap->size);
}

void max_delete(MaxHeap* max_heap, int* key_index, int key) { //O(logn)
 int index = key_index[key];
 increase_key(max_heap, key_index, index, INF);
 extract_max(max_heap, key_index);
}

void clear(MaxHeap* max_heap) {
 for (int i = 0; i < max_heap->size; i++)
 max_heap->heap[i] = N_INF; //assuming it is never in the heap
 max_heap->size = 0;
}

void print_heap(MaxHeap* max_heap) { // O(n)
 int size = max_heap->size;
 if (size % 2 != 0) 
 size = size + 1;
 for (int i = 0; i < size/2 - 1; i++) {
 printf("Parent: %d -> Left: %d | Right: %d \n", max_heap->heap[i], max_heap->heap[2*i+1], max_heap->heap[2*i+2]);
 }
 int j = max_heap->size/2 - 1;
 if (max_heap->size % 2 == 0)
 printf("Parent: %d -> Left: %d \n", max_heap->heap[j], max_heap->heap[2*j+1]);
}

int is_maxheap(MaxHeap* max_heap) { // O(n)
 for (int i = max_heap->size-1; i > 0 ; i--) {
 if (max_heap->heap[i] > max_heap->heap[parent(i)]) {
 return 0;
 }
 }
 return 1;
}

void heap_sort(MaxHeap* max_heap, int* key_index) { // assumes already a max heap as argument
 // if the input is not a heap, call build_max_heap()
 for (int i = max_heap->size - 1; i >= 0; i--) {
 swap(&max_heap->heap[0], &max_heap->heap[i]);
 max_heapify(max_heap->heap, key_index, 0, i);
 }
}

void print_arr(MaxHeap* max_heap) {
 for (int i = 0; i < max_heap->size; i++)
 printf("%d ", max_heap->heap[i]);
 printf("\n");
}

int main() {
 
 int size = 6, MAX_Key = INF, elements[6] = {10, 20, 15, 12, 40, 25};
 int* data = calloc(size, sizeof * data);
 if (!data) return 0;
 for (int i = 0; i < size; i++)
 data[i] = elements[i];
 int* key_index = calloc(MAX_Key, sizeof * key_index); // we assume key > 0, if key < 0, then we add an additional array
 if (!key_index) return 0;
 for (int i = 0; i < size; i++)
 key_index[elements[i]] = i;
 
 MaxHeap max_heap = maxheap_init;
 max_heap.size = size;
 max_heap.heap = build_max_heap(data, key_index, size);
 
 print_heap(&max_heap);
 printf("is_max_heap: %d \n", is_maxheap(&max_heap));
 extract_max(&max_heap, key_index);
 printf("is_max_heap: %d \n", is_maxheap(&max_heap));
 print_heap(&max_heap);
 max_insert(&max_heap, key_index, 14);
 printf("is_max_heap: %d \n", is_maxheap(&max_heap));
 print_heap(&max_heap);
 max_delete(&max_heap, key_index, 14);
 printf("is_max_heap: %d \n", is_maxheap(&max_heap));
 print_heap(&max_heap);
 printf("height: %d \n", height(&max_heap));
 printf("max: %d \n", get_max(&max_heap));
 heap_sort(&max_heap, key_index);
 print_arr(&max_heap);
 clear(&max_heap);
 printf("is empty: %d \n", is_empty(&max_heap));
 
 free(data);
 free(key_index);
 
 return 0;
}

```

If you have any improvement ideas, I would be very grateful to read through them. I should note that this implementation is for learning purposes, not for a client or something. There might be some place when I missed some secondary check for an empty array or something, but I am interested in seeing if the code holds or not. I tested it and it works just fine.