Use the code given below to implememt the following heapsort algorithm in C language.

#include #include #include #include #define NUM_NODES 7 #define EMPTY 1000 /// for Max-Heaps change to -1 struct heap_struct { unsigned int max_heap_size; unsigned int crnt_heap_size; int * elements; }; /***** Prototypes here *****/ struct heap_struct * create_heap(unsigned int max_elements); bool is_full(struct heap_struct * H); int insert_node(int x, struct heap_struct * H); void print_heap(struct heap_struct * H); int delete_root(struct heap_struct * H); void swap_ref(int * x, int * y); int main(void) { srand((unsigned int)time(NULL)); /// Random number generator seeded with value of time int my_array[NUM_NODES]; int i = 0; int j = 0; printf(" Array:\t\t"); while(i elements = (int *) malloc(sizeof(int) * (max_elements+1)); if(H->elements == NULL) { printf(" Fatal Error!! Out of memory!! "); exit(-1); } H->max_heap_size = max_elements; H->crnt_heap_size = 0; for(int x=0; xelements[x] = EMPTY; return H; } int insert_node(int x, struct heap_struct * H) { unsigned int i; if(is_full(H)) { printf(" Error! Heap is full !! "); return; } else { i = ++ H->crnt_heap_size; H->elements[i] = x; /// Insert the item in the first available position. while(((H->elements[i] elements[i/2])) && (i != 1)) /// Then move it up to its correct position { swap_ref(&(H->elements[i]), &(H->elements[i/2])); i = i/2; } } } bool is_full(struct heap_struct * H) { return((H->crnt_heap_size) == (H->max_heap_size)); } void print_heap(struct heap_struct * H) { printf(" Heap Capacity: %d", H->max_heap_size); printf(" Heap Size: %d", H->crnt_heap_size); printf(" Heap Data:\t"); for(int i = 1; i crnt_heap_size; i++) printf("%d\t", H->elements[i]); printf(" "); } int delete_root(struct heap_struct * H) /// Also returns the value of root to calling function { int index = H->crnt_heap_size; /// Now 'index' contains the index of the last node int root = H->elements[1]; /// We will return this value at the end of this function H->elements[1] = H->elements[index]; /// Replace the root with the last node H->elements[index] = EMPTY; /// Make the last slot empty /// Sink this value down till the heap property is satisfied int i = 1; /** While this newly promoted 'root' is larger than any of its children we will continue to swap it with the smaller of the two siblings until the heap property (node being smaller than all its children) is satisfied. **/ while(icrnt_heap_size/2) /// We just need to check the siblings of the 2nd last level { if(((H->elements[i])>(H->elements[2*i])) || ((H->elements[i])>(H->elements[(2*i)+1]))) { if((H->elements[2*i]) > (H->elements[(2*i)+1])) /// If the left child node is larger than the right child { swap_ref(&(H->elements[i]), &(H->elements[(2*i)+1])); i = (2*i)+1; } else { swap_ref(&(H->elements[i]), &(H->elements[2*i])); i = 2*i; } } else break; } H->crnt_heap_size --; /// Now there is one less item in the heap. return(root); } void swap_ref(int * x, int * y) { int temp = * y; *y = *x; *x = temp; }

HEAPSORT (ARR, N) Step 1: [Build Heap H] Repeat for I = 0 to N-1 CALL Insert_Heap (ARR, N, ARR[I]) [END OF LOOP] Step 2: (Repeatedly delete the root element) Repeat while N>O CALL Delete_Heap (ARR, N, VAL) SET N = N + 1 [END OF LOOP] Step 3: END Figure 14.12 Algorithm for heap sort