Q1)In this question, you are required to implement a set of min-heap operations in MIPS assembly language. Fundamental property of a min-heap is that for every node i other than the root, A[parent(i)] ? A[i], that is, the value of a node is at most the value of its parent. (For more information check a textbook on data-structures [2]).

The first element in the heap array A[0] is the size of the heap, i.e. the number of elements in the heap (i.e the integer size) is in A[0]. The rest of the elements in A (A[1] to A[size]) are the values in the nodes of the heap. If a node is at the kth location in the array, its children will be at the (2k) and the(2k+1) locations of the array. The following figures gives three different min- heaps which have 6, 4 and 3 nodes.

Procedures of the Question 1 There will be three procedures for this question: insert, delete, and print.

a) insert (value, heap) This procedure creates a new element (where the value is given in $a0 register) and insert it at the correct location in the min-heap by preserving heap-order property. The address of the place where the procedure should create the data structure is in heap (given in $a1). You should create a sufficient amount of memory for the heap. The register $v0 will contain the position number in the heap array A; i.e., it will be n, if A[n] is the location where the new value was inserted.

b) delete (heap) This procedure deletes the minimum value (i.e., the root node in logical structure of the tree) from the min-heap, where the address of the first item of the data structure is in heap argument. You should do appropriate modifications so that resulting min-heap should preserve heap-order property for all existing nodes.

c) print (heap) This procedure prints both the size (i.e., the number of integers) and the content of the min- heap structure on the screen. Each line of the output is for one level of the tree nodes stored in the array A. If there is no children (left or right), there will be x character to represent no node.

Example output of the print procedure for the min-heap structure represented in Figure 1.a is : The size of the heap is 6. [1] 6 [2]12 [3]7

[4]18 [5]19 [6]9x

Example output of the same procedure for the min-heap structure represented in Figure 1.b is : The size of the heap is 4. [1] 6 [2]9 [3]7

[4]10 x xx