implement a method to convert a maxheap of strings stored in an array into a min
ID: 3772802 • Letter: I
Question
implement a method to convert a maxheap of strings stored in an array into a minheap. Reminder: in amax heap the priority value at any node isthose at its children, while in a min heap, the priority valueat any node isthose at its children. The strings are by themselves priorities: if a string comes “before”another in alphabetical order, it is considered to be “less”, and is of lower priority.The method returns a new array–the original array is NOT modied. Your method must be thefastestpossible (bigOwise). You maydene andfully implementhelper methods as necessary. (Fully implemented means you may NOT “call”any method that you have not yourelf implemented here.)// Converts a max heap (stored in an array) into a new min heap.// Returns a new array that contains the min heap// The input array is NOT modifiedpublic static String[] convertMaxHeapToMin(String[] items) {// IMPLEMENT THIS METHOD
Explanation / Answer
ANSWER:
/**Complete Program that converts Max heap into min Heap**/
public class MaxToMin
{
//BUILD MIN HEAP
public static void constructMinHeap(int p,String[] minItems)
{
if(p>=(minItems.length/2)&&p<=minItems.length)
{
if(minItems[p].compareTo(minItems[p*2])>0 ||minItems[p].compareTo(minItems[p*2+1])>0)
{
if(minItems[p*2].compareTo(minItems[p*2+1])<0)
{
String t=minItems[p];
minItems[p]=minItems[p*2];
minItems[p*2]=minItems[p];
constructMinHeap(p*2,minItems);
}
else
{
String t=minItems[p];
minItems[p]=minItems[p*2+1];
minItems[p*2+1]=minItems[p];
constructMinHeap(p*2+1,minItems);
}
}
}
}
//MMETHOD CONVERTSMAX HEAP INTO MIN HEAP
public static String[] convertMaxHeapToMin(String[] items)
{
String[] minItems=items;
for(int k1=(minItems.length/2);k1>=1;k1--)
{
constructMinHeap(k1,minItems);
}
return minItems;
}
//MAIN METHOD
public static void main(String[] args)
{
String[] items={"z","y","x","w","v","t","u"};
System.out.println(convertMaxHeapToMin(items).toString());
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.