Create a Java Progarm for the following: Thank You =) Problem #1: (a) Consider a
ID: 3904721 • Letter: C
Question
Create a Java Progarm for the following:
Thank You =)
Problem #1: (a) Consider a binary min-heap. We have a method that print the keys as encountered in a preorder traversal. Is the output sorted? Justify your answer. Attempt the same question for inorder and postorder traversal. (b) Propose an efficient algorithm (only pseudocode) to find all nodes less than some value X in a binary min-heap. Analyze its complexity. (c) Write (in Java) a method replaceKey in the MaxHeap class with the following signature: public void replacekey(Integer oldkey, Integer newkey) The method will replace the first occurrence of oldKey with the newKey, and restore the Max-Heap property after the change. If the oldKey does not exist in the heap, the method prints an appropriate message and returns without changing the heap. Example: Suppose our binary heap object (bh) has the following keys: 99 64 4254 32 28 6 197 26 4 Then the method call: bh.replaceKey (new Integer(54), new Integer(105) should change the keys to: 105 99 4264 32 28 6197 264 Note: You can assume that the methods perlocateUp and perlocateDown are already implemented in your MaxHeap class.Explanation / Answer
Implemented source code:-
----------------------------------
package com.bel;
import java.util.Arrays;
public class Heap_Sort
{
public int array[];
public Heap_Sort(int[] array)
{
this.array = array;
}
public void makeHeap()
{
int temp;
int index;
for(int i=0;i<array.length;i++)
{
index= i;
while (index != 0)
{
int parent = (index - 1) / 2;
if (array[index] <= array[parent])
{
break;
}
// swap child element to its parent one
temp = array[index];
array[index] = array[parent];
array[parent] = temp;
index = parent;
}
}
}
public void removekeys(int count)
{
int leftChild;
int rightChild;
int parentGreat;
int temparray = array[0];
array[0] = array[count];
array[count] = temparray;
int index = 0;
count--;
while (true)
{
leftChild=index*2+1;
rightChild=index*2+2;
// check the boundary
if (rightChild > count)
break;
if (array[index] > array[leftChild] && array[index] > array[rightChild])
break;
parentGreat= array[rightChild] > array[leftChild] ? rightChild : leftChild;// to get greater parent
// swap current item to its parent one
int temp = array[index];
array[index] = array[parentGreat];
array[parentGreat] = temp;
index = parentGreat;
}
}
public String heapSort()
{
makeHeap();//Calling Make heap Method
for (int i=array.length-1;i>0;i--)
{
removekeys(i);
}
return Arrays.toString(array);
}
public static void main(String[] args)
{
int Array[]={7,8,5,9,3,2,6,4,1,10};
System.out.println("Before sorting Array Elements are:"+Arrays.toString( Array));
Heap_Sort obj=new Heap_Sort(Array);
String SortedArray=obj.heapSort();
System.out.println(" The Sorted Array elemnts are:"+SortedArray);
}
}
sample output:-
--------------------
Before sorting Array Elements are:[7, 8, 5, 9, 3, 2, 6, 4, 1, 10]
The Sorted Array elemnts are:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]