Here is the heapsort algorithm void Heapsort (int heap, int N) // Organize the a
ID: 3597250 • Letter: H
Question
Here is the heapsort algorithm void Heapsort (int heap, int N) // Organize the array in a heap (buildheap) downheap (heap, N, k); // remove each node in turn while (N 1) { int tempo -heap [1]; heap [1] = heap [N]; heap [N] = tempo; downheap (heap, N, 1); NOTE: downheap(heap,N,i): do downheap operation for the node at index i, knowing the heap ends at index N a) Give the algorithm of the method downheap in the case of a max-heap b) Sort the arrays below using this heapsort. Give the State of the table after each call to the function downheap. 2 3 8 21 4 32 8 NOTE: The implementation in this question assumes heap is stored in positons 1..N of the array In the textbook and lab, the implementation uses positions O..N-1 In the lecture notes we discuss both types of implementationExplanation / Answer
Please find my code for downheap function.
Please repost other questions in separate post.
/* Function to swap largest element in heap */
public static void downheap(int arr[], int N, int i)
{
int left = 2*i ;
int right = 2*i + 1;
int max = i;
if (left <= N && arr[left] > arr[i])
max = left;
if (right <= N && arr[right] > arr[max])
max = right;
if (max != i)
{
int tmp = arr[i];
arr[i] = arr[max];
arr[max] = tmp;
downheap(arr, N, max);
}
}