#include  #include  #define MAXVAL 10000 #define LENGTH 120 int child_index(int curr_node, int child_num); /* Child num starts from 0 */ int is_max_heap(int * array, int length); int rand_int(int range); void init_random(); int * create_rand_array(int length); void swap(int * array, int i, int j); void perc_down(int curr_node, int * array, int length); void heapify(int * array, int length); void destroy_rand_array(int * array); void main() { int * array = create_rand_array(LENGTH); printf("Create a random array of integers: "); printf("Does it have the max heap property? "); if (is_max_heap(array,LENGTH)==1) printf("yes "); else printf("no "); printf("Heapify the array: "); heapify(array,LENGTH); printf("Does it have the max heap property? "); if (is_max_heap(array,LENGTH)==1) printf("yes "); else printf("no "); destroy_rand_array(array); } int child_index(int curr_node, int child_num) /* Child num starts from 0 */ { return curr_node*3 + child_num+1; } int is_max_heap(int * array, int length) { for (int curr_node=0; child_index(curr_node,0)=0; curr_node--) { perc_down(curr_node, array, length); } } void destroy_rand_array(int * array) { free(array); } 

Problem 1 (It's similar to Problem 6-2 in the textbook CLRS page 179). A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children. Consider a d-ary heap that's implemented in an integer array a [ ], and starts from index 0 , i.e., a[0] is the root of the tree. The d-ary heap has the max heap property, where a node is at least as large as any of its children. (a) [1 pt] Consider a node in the heap at index k that has a parent and d children. What are the indices of its parent, and children? (b) [1pt] What is the height of the heap if it had n elements? (c) [1 pt] Attached is a program heap.c. It has a function void heapify(int a[ ], int length), which will build a 3-ary heap from an array of values a [ ] of length 'length'. It requires a helper function void perc_down(int k, int a, int length), which causes a downward percolation from the node at index k. The helper function doesn't work. Rewrite it so that it does work and upload your heap.c in laulima. Note that there's another function check_heap that returns 1 if the heap has the max heap property, and returns 0 otherwise. The output should look like this: Create a random array of integers: Does it have the max heap property? no Heapify the array: Does it have the max heap property? yes