********IN JAVA**********

The problem is to convert the given Max Heap into a binary search tree (BST) with the condition that the final BST needs to be also a complete binary tree.

Note We assume that:

- The number of elements in the Max Heap tree is always 2^L - 1 , which L is the number of levels in the tree.

- There is no duplicate element in the Max Heap.

Example:

Input (max heap):

7 / \ 6 5 / \ / \ 3 4 1 2

Output (BST):

4 / \ 2 6 / \ / \

1 3 5 7

*******************************************

Do not edit the main or Max Heap!

*******************************************

import java.util.*;

import java.lang.*;

import java.io.*;

class MaxHeap> {

private java.util.ArrayList list = new java.util.ArrayList<>();

/** Create a default heap */

public MaxHeap() {

}

/** Create a heap from an array of objects */

public MaxHeap(E[] objects) {

for (int i = 0; i < objects.length; i++)

add(objects[i]);

}

/** Add a new object into the heap */

public void add(E newObject) {

list.add(newObject); // Append to the heap

int currentIndex = list.size() - 1; // The index of the last node

while (currentIndex > 0) {

int parentIndex = (currentIndex - 1) / 2;

// Swap if the current object is greater than its parent

if (list.get(currentIndex).compareTo(

list.get(parentIndex)) > 0) {

E temp = list.get(currentIndex);

list.set(currentIndex, list.get(parentIndex));

list.set(parentIndex, temp);

}

else

break; // the tree is a heap now

currentIndex = parentIndex;

}

}

/** Remove the root from the heap */

public E remove() {

if (list.size() == 0) return null;

E removedObject = list.get(0);

list.set(0, list.get(list.size() - 1));

list.remove(list.size() - 1);

int currentIndex = 0;

while (currentIndex < list.size()) {

int leftChildIndex = 2 * currentIndex + 1;

int rightChildIndex = 2 * currentIndex + 2;

// Find the maximum between two children

if (leftChildIndex >= list.size()) break; // The tree is a heap

int maxIndex = leftChildIndex;

if (rightChildIndex < list.size()) {

if (list.get(maxIndex).compareTo(

list.get(rightChildIndex)) < 0) {

maxIndex = rightChildIndex;

}

}

// Swap if the current node is less than the maximum

if (list.get(currentIndex).compareTo(

list.get(maxIndex)) < 0) {

E temp = list.get(maxIndex);

list.set(maxIndex, list.get(currentIndex));

list.set(currentIndex, temp);

currentIndex = maxIndex;

}

else

break; // The tree is a heap

}

return removedObject;

}

/** Get the number of nodes in the tree */

public int getSize() {

return list.size();

}

}

class BST {

TreeNode root;

// insert method to add elements to BST

public void insert(int key){

TreeNode newNode = new TreeNode(key);

if(root == null){

root = newNode;

}else{

TreeNode current = root;

TreeNode parent;

while(true){

parent = current;

if(key < current.element){

current = current.left;

if(current == null){

parent.left = newNode;

return;

}

}else{

current = current.right;

if(current == null){

parent.right = newNode;

return;

}

}

}

}

}

//Print the elements of the BST level by level staring from root

public void breadthFirst(){

Queue q = new LinkedList();

if(root!= null)

q.add(root);

while(!q.isEmpty()){

TreeNode current = (TreeNode) q.remove();

System.out.print(current.element + " " );

if(current.left != null)

q.add(current.left);

if(current.right != null)

q.add(current.right);

}

}

private class TreeNode {

int element;

TreeNode left;

TreeNode right;

public TreeNode(){}

public TreeNode(int e){

this.element = e;

}

}

}

*********MAIN DRIVER HERE**************

class DriverMain{

public static void main(String args[]){

Scanner input = new Scanner(System.in);

String str = input.nextLine();

input.close();

int[] list = Arrays.stream(str.substring(0, str.length()).split("\\s"))

.map(String::trim).mapToInt(Integer::parseInt).toArray();

// create Max heap and adding the elements

MaxHeap maxHeap= new MaxHeap();

for (int i = 0; i < list.length; i++)

maxHeap.add(list[i]);

//convert the BFS to MaxHeap

BST bsTree = HW8_P3.convert(maxHeap);

// print BST using BFS (level by level order)

bsTree.breadthFirst();

}

}

*****************************************

*****************************************

Here is where to write the code!

*****************************************

*****************************************

class HW8_P3{

// write your code, you can add more methods

public static BST convert(MaxHeap maxHeap){

}

}

***********************************************

Comments in the code are appreciated!