please answer in C
Step 3: Modify your min-heap that stores arbitrary structs
[Don't forget! This reading should be helpful (Links to an external site.)!]
We frequently want to sort items that aren't just ints. In C, that requires us to incorporate 2 things: void* and function pointers. void* is basically just a pointer to *something*; we don't know what type it's pointing to: only the calling code knows that. But, our code can do something with that type even if we don't know what it really is. A function pointer is similar to the idea of a void*: it's a pointer to a function that we've defined elsewhere (it lives in memory somewhere, kind of like a named variable), and we can call that function. It kinda treats functions like variables!
To create a min-heap that can sort *any datatype*, we'll utilize void* and function pointers.
- Heap* CreateHeap(void** data, int num_elems, int (*Compare)(void*, void*)) returns an empty heapH that is set up to store at mostn elements. This operation takes O(N) time, as it involves initializing the array that will hold the heap.
- void Insert(Heap* heap, int val) inserts the intval into heapheap. If the heap currently hasn elements, this takes O(log n) time.
- void* ExtractMin(Heap* heap) identifies and deletes an element with minimum value from a heap.
- void* Delete(Heap* heap, int position) deletes the element in heap positioni. This is implemented in O(log n) time for heaps that haven elements.
- void BubbleUp(Heap* heap, int index) bubbles the element at location index up to its correct position.
- void BubbleDown(Heap* heap, int index) bubbles the element at location index down to its correct position.
- void Swap(Heap* heap, int first_ind, int second_ind) swaps the elements located at first_ind and second_ind in the heap.
- DestroyHeap(Heap* heap) frees all resources associated with heapheap.
There are 2 modifications to the heap implementation here:
Changing "int" to "void*". This allows our heap to store void*s instead of ints, where a void* is a pointer to some arbitrary struct.
Including a "Compare" function in our heap. When we create the heap, we pass in a "Compare" function. This is the function that will be used to compare the arbitrary structs in our heap. This signature (int (*Compare)(void*, void*)) says that a compare function must return an int, and take in a pointer to two places in memory. See the int_helpers.c and score.c file in Github for an example.
I've provided some code to help you test your implementation-- you'll find this in run_gen_heapsort.c. You should be able to build and run it from the beginning. Here's what it looks like before you implement the code:
make ./run_gen_heapsort [44 23 9 43 26 1 1 10 0 45 28 43 16 17 10 42 ] [44 23 9 43 26 1 1 10 0 45 28 43 16 17 10 42 ]
After you finish implementing the functions in gen_heap.c and gen_heapsort.c, the values in the second line should be sorted.