Matching.

This exercise is about tracing the execution of Build-Max-Heap(A). Below is the pseudo code of Build-Max-Heap(A).:

Consider the heap below (drawing it as a tree may help you work out this exercise) represented as an n-element array A with n = heap_size = 10.The first row shows the indices of Array A while the second row shows the keys in the heap.

i	1	2	3	4	5	6	7	8	9	10
key	4	16	9	8	1	10	3	14	2	7

Execute Build-Max-Heap(A) on the heap above and report on the table below the nodes that are changed by the execution of Build-Max-Heap(A).

On the table below, the first (leftmost) column list the nodes that will change from the earliest to the latest. When a key exchange between nodes occurs, we assume that the node at the deepest level changes first. For each node, provide its index and the new value of its key.

The first row to fill in is related to the first node to change its key. Provide its index and its new key.

The second row to fill in is related to the second node to change its key. Provide its index and its new key...... on so on

Nodes Changing	Index i	(Key)
1st Node to change
2nd Node to change
3rd Node to change
4th Node to change