write c program that void sift_up(int *arr, int pos);

// sift down min-heap operation
// GIGO if arr is NULL, if pos is outside the array, or len is incorrect

Question

write c program that void sift_up(int *arr, int pos);

// sift down min-heap operation
// GIGO if arr is NULL, if pos is outside the array, or len is incorrect

Accepted Answer

```c // Function to perform the sift up operation in a min-heap void sift_up(int *arr, int pos) { // While the current position is not the root and the parent is greater than the current node while (pos > 0 && arr[(pos - 1) / 2] > arr[pos]) { // Swap the current node with its parent int temp = arr[pos]; arr[pos] = arr[(pos - 1) / 2]; arr[(pos - 1) / 2] = temp; // Move up to the parent's position pos = (pos - 1) / 2; } } ``` ```c // Main function to test the sift_up function int main() { // Test case 1: Sift up last element in a min-heap int heap1[] = {1, 3, 2, 17}; sift_up(heap1, 3); assert(heap1[0] == 1 && heap1[1] == 3 && heap1[2] == 2 && heap1[3] == 17); // Test case 2: Sift up an element in a min-heap to the root int heap2[] = {5, 3, 2, 1}; sift_up(heap2, 3); assert(heap2[0] == 1 && heap2[1] == 3 && heap2[2] == 2 && heap2[3] == 5); return 0; } ``` ∻Explanation∻ ⚹The `sift_up` function is used to maintain the heap property in a min-heap after a change in a node's value that might be smaller than its parent's value. The function swaps the node with its parent until the heap property is restored.⚹ ∻Step-by-step Instruction∻ ‖ ▪ ⋮ Define the `sift_up` function that takes an array and a position as arguments. ‖ ‖ ▪ ⋮ Use a while loop to compare the current node with its parent and swap if necessary. ‖ ‖ ▪ ⋮ Continue the loop until the current node is at the root or no longer less than its parent. ‖ ‖ ▪ ⋮ Define the main function to test the `sift_up` function with specific use cases. ‖ ‖ ▪ ⋮ Use assertions to verify that the heap property is maintained after the `sift_up` operation. ‖ ∻Time Complexity∻ ⚹The time complexity of the sift_up function is O(log n) because in the worst case, a node may need to be swapped up through the height of the heap, which is logarithmic relative to the number of elements.⚹ ∻Space Complexity∻ ⚹The space complexity is O(1) as the operation is performed in place and no additional space is used apart from temporary variables.⚹

Sia