I really don't like the key_index array being a separate data structure that needs to be passed into all functions that work on the heap. It probably needs to be part of the heap data structure. But since I don't now why it's there or what its use case is, I won't comment on this further.

I really don't like the key_index array being a separate data structure that needs to be passed into all functions that work on the heap. It needs to be part of the heap data structure.

It seems that the key_index array is only read in delete_key(), everywhere else it is just updated. This is a lot of bookkeeping for the benefit of being able to delete a specific value from the heap in O(log n). I've never written a heap with this ability, I don't know if I'd do it the same way. If an O(n) delete is OK (you don't delete often), then consider just looking through the heap to find the key. If you delete often, is a heap the right data structure?

Also, key_index being an array means that keys must be small non-negative integers. Consider using a hash table instead.

What if you want to insert() a value that is larger than what fits in key_index? You don't check for this in insert()!

The biggest issue I see here, and is not yet commented on, is the call to realloc for every insertion. When you remove an element from the heap, the size value is changed but the memory block (array) is not.

So when you remove one element and then insert another, the realloc call does nothing, as the array has the right size. But what happens if you remove two elements, and then insert one? realloc will reduce the array size by 1. For the next insertion the array has to grow again. Hopefully your implementation of realloc will not look for a new memory block here and copy data over...

In any case, increasing the array size by 1 every time you insert an element is expensive, it makes the insertion operation have a cost of O(n) instead of O(log n), because the array needs to be copied over. Typically we double the array size when we run out of space, so that the insertion operation remains of O(log n). You can accomplish this by separating the array size and the number of elements in the heap. This is slightly more bookkeeping, for the benefit of faster insertions, and no need for that marker value (the heap is empty if the "number of elements" variable is 0). For example:

typedef struct MaxHeap {
    int* heap;     // pointer to array
    int size;      // number of elements stored in array
    int capacity;  // size of array
} MaxHeap;

Another issue is that the heap insertion reallocates the array, changing the max_heap.heap pointer, but not the data pointer in main(), which now might point to deallocated memory. At the end of the program, data is freed (a potential exception), but not max_heap.heap (a potential memory leak).

I think it is cleaner if MaxHeap owns the data it points to, and at the end of the program you call some function that frees the data in the heap, say free_maxheap(max_heap). For best effect, you'd actually use create_maxheap(), so that the heap allocates its own data array. You should not have a function like build_max_heap() that takes a pointer from the caller and keeps it. Currently it is unclear to the caller: can I free the pointer after calling build_max_heap()? No, because the pointer is still being used, though this is not documented anywhere. It is much cleaner if the caller passes a pointer to data, but the data is copied over into the heap. If for efficiency you want to have a function that takes ownership of the input pointer, then this needs to be clearly documented, both in comments and in the function name (maybe create_maxheap_with_array()?).

The biggest issue I see here, and is not yet commented on, is the call to realloc for every insertion. When you remove an element from the heap, the size value is changed but the memory block (array) is not.

So when you remove one element and then insert another, the realloc call does nothing, as the array has the right size. But what happens if you remove two elements, and then insert one? realloc will reduce the array size by 1. For the next insertion the array has to grow again. Hopefully your implementation of realloc will not look for a new memory block here and copy data over...

In any case, increasing the array size by 1 every time you insert an element is expensive, it makes the insertion operation have a cost of O(n) instead of O(log n), because the array needs to be copied over. Typically we double the array size when we run out of space, so that the insertion operation remains of O(log n). You can accomplish this by separating the array size and the number of elements in the heap. This is slightly more bookkeeping, for the benefit of faster insertions, and no need for that marker value (the heap is empty if the "number of elements" variable is 0). For example:

typedef struct MaxHeap {
    int* heap;     // pointer to array
    int size;      // number of elements stored in array
    int capacity;  // size of array
} MaxHeap;

Another issue is that the heap insertion reallocates the array, changing the max_heap.heap pointer, but not the data pointer in main(), which now might point to deallocated memory. At the end of the program, data is freed (a potential exception), but not max_heap.heap (a potential memory leak).

I think it is cleaner if MaxHeap owns the data it points to, and at the end of the program you call some function that frees the data in the heap, say free_maxheap(max_heap). For best effect, you'd actually use create_maxheap(), so that the heap allocates its own data array. You should not have a function like build_max_heap() that takes a pointer from the caller and keeps it. Currently it is unclear to the caller: can I free the pointer after calling build_max_heap()? No, because the pointer is still being used, though this is not documented anywhere. It is much cleaner if the caller passes a pointer to data, but the data is copied over into the heap. If for efficiency you want to have a function that takes ownership of the input pointer, then this needs to be clearly documented, both in comments and in the function name (maybe create_maxheap_with_array()?).

I really don't like the key_index array being a separate data structure that needs to be passed into all functions that work on the heap. It probably needs to be part of the heap data structure. But since I don't now why it's there or what its use case is, I won't comment on this further.