#8-150 40 170 50 160 28 10 195 a) Use Mergesort to sort the following list. (Hin
ID: 3740968 • Letter: #
Question
#8-150 40 170 50 160 28 10 195 a) Use Mergesort to sort the following list. (Hint: Use the algorithm 2.4, p.62) *Show the action steps Give the tree recursive calls b) Use Quicksort to sort the following list. Show the action steps. (Hint: Use algorithm 2.6, p.65) * Show the action steps Give the tree recursive calls c) Use Heapsort to sort the following list. Show the action steps * Show the action steps Give the tree recursive calls (Maxheap) #9-write an algorithm that checks if an essentially complete binary tree is a heap. #10-Use the divide-and-conquer approach to write an algorithm that finds the smallest item in a list of n itemsExplanation / Answer
Algorithm to check binary tree is heap
class BinaryTreeNode
{
int key;
Node left, right;
Node(int k)
{
key = k;
left = right = null;
}
}
class Is_BinaryTreeHeap
{
int countNodes(Node root)
{
if(root==null)
return 0;
return(1 + countNodes(root.left) + countNodes(root.right));
}
boolean isTreeComplete(Node root, int index, int number_nodes)
{
if(root == null)
return true;
if(index >= number_nodes)
return false;
return isCompleteUtil(root.left, 2*index+1, number_nodes) &&
isTreeComplete(root.right, 2*index+2, number_nodes);
}
boolean isHeapUtil(Node root)
{
if(root.left == null && root.right==null)
return true;
if(root.right == null)
{
return root.key >= root.left.key;
}
else
{
if(root.key >= root.left.key && root.key >= root.right.key)
return isHeapUtil(root.left) && isHeapUtil(root.right);
else
return false;
}
}
boolean isHeap(Node root)
{
if(root == null)
return true;
isTreeComplete()
int node_count = countNodes(root);
if(isTreeComplete(root, 0 , node_count)==true && isHeapUtil(root)==true)
return true;
return false;
}
// driver function to test the above functions
public static void main(String args[])
{
Is_BinaryTreeHeap btree= new Is_BinaryTreeHeap();
Node root = new Node(10);
root.left = new Node(9);
root.right = new Node(8);
root.left.left = new Node(7);
root.left.right = new Node(6);
root.right.left = new Node(5);
root.right.right = new Node(4);
root.left.left.left = new Node(3);
root.left.left.right = new Node(2);
root.left.right.left = new Node(1);
if(btree.isHeap(root) == true)
System.out.println("binary tree is a Heap");
else
System.out.println("inary tree is not a Heap");
}
}
Divide and Conquer to find smallest
Divide and conquer aapproch is to do process by dividing array into two parts
1 to n/2 and n/2 +1 to n
public static int findSmallest(int[] array) {
if (array.length == 1) {
return array[0];
}
int array1[] = Arrays.copyOfRange(array, 0, array.length / 2);
int array2[] = Arrays.copyOfRange(array, array.length / 2, array.length);
return Math.min(smallest(array1), smallest(array2));
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.