” 辅导CSE310语言程序、 写作C++设计编程CSE310 Project 2: Min-HeapIn your second programming project, you will expand your first project. As in the case ofthe first programming project, it should be implemented in C++, on a Linux platform such asgeneral.asu.edu. Your program will be graded on Gradescope, which uses a Linux platform. Youwill continue to have modular design, provide a Makefile to compile various modules to generatethe executable file named run. Among other things, you need to have1. a main program, which coordinates all other modules;2. a module that provides utility services including command line interpretation;3. a module that implements the min-heap data structure (all heap functions);4. a Makefile which compiles all modules and link them into the executable.For each module other than the main program, you should have a header file which specifiesthe data structures and the Prototypes of the functions in the module, and an implementationfile which implements all of the functions specified in the header file. All programs will becompiled and graded on Gradescope. If your program works well on general.asu.edu, thereshould not be much problems. You will need to submit it electronically on Gradescope via the linkon Canvas. Test cases are posted on Canvas. If your program does not compile and work onGradescope, you will receive 0 on this project.You need to define the following data types. ELEMENT is a struct that contains a field named key, which is of type int. HEAP is a data type that contains three fields named capacity (of type int), size (of typeint), and H (of type **ELEMENT). H will be pointing to an array of capacity + 1 of pointersof type *ELEMENT. Note that the size of HEAP should be equal to 12, regardless of the capacityor the size of the heap. In Other words, sizeof(HEAP) should always return 12.The functions that you are required to implement are: Initialize(value) which creates an object of type HEAP with capacity equal to value, sizeequal to 0, and H points to a dynamically allocated array of value+1 pointers. It then returnsa pointer to this object. This function requires you to perform dynamic memory allocation,given the demand value. Note that you have already done this in your first project. PrintHeap(heap) which prints out the information of the heap pointed to by heap, includingcapacity, size, and the key fields of the elements in the array with index going from 1 tosize. Note that you have already done this in your first project. WriteHeap(heap) which opens the file named HEAPoutput.txt in write mode and write thethe information of the heap pointed to by heap to the file. The format of HEAPoutput.txtshould be identical to that of HEAPinput.txt.1 Insert(heap, element) which inserts an object of type ELEMENT pointed to by element intothe heap pointed to by heap. ExtractMin(heap) which deletes the minimum element from the heap pointed to by heap. DecreaseKey(heap, index, value) which decreases the key of heap-H[index] to value. min-Heapify(heap, index) Which performs the heapify function at index of the array pointedto by heap-H.You are free to include additional parameters as you see fit and decide the return types of thefunctions. You should implement a module that takes the following commands from stdin andfeeds to the main program: S P W C value R flag I value D flag K index valueThe main program should react to each of the above commands in the following way.S: On reading S, the program1. Stops.P: On reading P, the program does the following:1. If heap is NULL, writes the following line to stdout:Error: cannot printand waits for the next command from stdin.2. Writes the information of the heap pointed to by heap to stdout. Refer to the postedtest cases for output format.3. Waits for the next command from stdin.W: On reading W, the program does the following:1. Opens the file HEAPout.txt in write mode. If the file is not opened successfully, orheap is NULL, writes the Following line to stdout:2Error: cannot writeand waits for the next command from stdin.2. Writes the information of the heap pointed to by heap to the file HEAPoutput.txt.HEAPoutput.txt should have exactly the same format as HEAPinput.txt.3. Waits for the next command from stdin.C: On reading C value, the program does the following:1. Calls a function in the heap module to create a heap with capacity equal to value andsize equal to 0, and return a pointer to this heap object to the caller.2. Waits for the next command from stdin.R: On reading R flag, the Program does the following:1. Opens the file HEAPinput.txt in read mode. If the file is not opened successfully,writes the following line to stdout:Error: cannot open file for readingand waits for the next command from stdin.2. Reads in the first integer, n, from the file opened.If heap is NULL or heap-capacity is smaller than n, writes the following line to stdout:Error: heap overflowand waits for the next command from stdin.3. Reads in the next n integers key1, key2, . . ., keyn from the file, dynamically allocatesmemory for an ELEMENT, sets it key to keyj, and let heap-H[j] points to this ELEMENT,for j = 1, 2, . . . , n.4. Calls the BuildHeap within the heap module to build a min heap on the array H usingthe linear time buildheap algorithm. Note that you have to change the algorithmaccordingly to build a min-heap, not a max-heap.5. If flag is equal to 1, your program should write to stdout the number of min-Heapifyfunctions called by this BuildHeap call. Refer to the test cases for the output format.6. Waits for the next command from stdin.D: On reading D flag, the program does the following:1. If heap is NULL or heap-size is 0, writes the following line to stdout:Error: heap is NULL or emptyand waits for the next command from stdin.2. Deletes the minimum Element from the heap and writes to stdout the key of the deletedelement. Refer to the test cases for output format.33. If flag is equal to 1, your program should write to stdout the number of min-Heapifyfunctions triggered by this delete-min operation. Refer to the test cases for the outputformat.4. Waits for the next command from stdin.I: On reading I value, the program does the following:1. If heap is NULL or heap-size is equal to heap-capacity, writes the following line tostdout:Error: heap is NULL or fulland waits for the next command from stdin.2. Dynamically allocates memory for an ELEMENT, sets its key field to value, and inserts itto the heap pointed to by heap.3. Waits for the next command from stdin.K: On reading K index value, the program does the following:1. If heap is NULL or index is not within the interval [1, heap-size], or value is greaterthan or equal to heap-H[index]-key, writes the following line to stdout:Error: invalid call to DecreaseKeyand waits for the next command from stdin.2. Perform the corresponding decrease key operation: decrease the key of heap-H[index]to value by calling the DecreaseKey function in the heap module.3. Waits for the next command from stdin.The file HEAPinput.txt is a text file. The first line of the file contains an integer n, whichindicates the number of array elements. The next n lines contain n integers, one integer per line.These integers are the key values of the n array elements, from the first element to the nth element.Refer to the posted test cases for the exact format of HEAPinput.txt.Grading policies: (Sample test cases are posted on Canvas.) All programs will be graded onGradescope. If your program Does not compile and execute on Gradescope, you will receive 0 forthis project. So start working today, and do not claim my program works perfectly on my PC,but I do not know how to use Gradescope.(0 pt) You should provide a Makefile that can be used to compile your project on Gradescope. Theexecutable file should be named run. If your program does not pass this step, you will receive0 on this project.(60 pts) You will earn 5 points for each of the 12 posted test cases your program passes on Gradescope.(20 pts) You will earn 5 points for each of the 4 unposted test cases your program passes on Gradescope.You should try to make your Program as robust as possible. A basic principle is that yourprogram can complain about bad input, but should not crash.如有需要，请加QQ：99515681 或WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
