Please help me write this code in Java 8 . The question shows sample code in C++
ID: 3741890 • Letter: P
Question
Please help me write this code in Java 8. The question shows sample code in C++, but the final code should be written in Java 8. Please make sure that the code meets all the needed requirements mentioned in the question under each part such as in INPUT FORMAT, OUTPUT FORMAT, AND CONSTRAINTS. Can you also make sure to comment the code? Also, include screenshots of your input and output which should match the one in the question.
I have asked this question twice before, but got a completely wrong answer that didn't meet the requirements so please provide me with the correct answer. Thank You!
-----------------------------------------------------------------------------
This is the Sample Input and the sample output given in the question. The first number in the input is how many commands there should be inputted, followed by a blank line to end the commands as mentioned in the INPUT section of the question. Please make sure that your results match this and that they also meet all the requirements in the question under INPUT FORMAT, CONSTRAINTS, and OUTPUT FORMAT:
For this assignment, you will implement a max heap using an array for underlying storage. For example, in C++, the class definition would look like: class MaxHeap vector data You will need to implement size, which returns the number of items in the heap, max lookup, which returns the max element in the heap, extract max, which removes the max element from the heap, insert, which adds an item to the max heap, and delete, which removes the item at an arbitrary index from the max heap. For example, in C++, the function headers would be the following class MaxHeapf vector data public: MaxHeap) int size() [ int maxLookup O void extractMax) void insert (int data) [ void remove (int index) [Explanation / Answer
Please find the code below
CODE
========================
import java.util.ArrayList;
import java.util.Scanner;
public class MaxHeap {
ArrayList<Integer> heap;
int size;
public MaxHeap() {
heap = new ArrayList<>();
size = 0;
}
public int parent(int pos) {
assert pos > 0 : "Position has no parent";
return (pos-1)/2;
}
public void maxHeapify(int index) {
int largest = index;
int leftIndex = 2 * index + 1;
int rightIndex = 2 * index + 2;
if (leftIndex < size && heap.get(leftIndex) < heap.get(leftIndex)) {
largest = leftIndex;
}
if (rightIndex < size && heap.get(largest) < heap.get(rightIndex)) {
largest = rightIndex;
}
if (largest != index) {
swap(index, largest);
maxHeapify(largest);
}
}
public void buildMaxHeap() {
for (int i = size / 2 - 1; i >= 0; i--) {
maxHeapify(i);
}
}
/**
* Insert a new element into the heap satisfying
* the heap property.
*
* Time complexity: O(log n) where 'n' is total no. of
* elements in heap or O(h) where 'h' is the height of
* heap.
*
* @param elem
*/
public void insert(int elem) {
// increase heap size
int i = size;
int parentIndex = (int) Math.floor((i - 1) / 2);
// move up through the heap till you find the right position
while (i > 0 && elem > heap.get(parentIndex)) {
heap.add(i, heap.get(parentIndex));
i = parentIndex;
parentIndex = (int) Math.floor((i - 1) / 2);
}
heap.add(i, elem);
size++;
}
public int remove(int index) {
assert (index >= 0) && (index < size) : "Illegal heap position";
if (index == (size-1))
size --; // Last element, no work to be done
else
{
swap(index, --size); // Swap with last value
// If we just swapped in a big value, push it up
while ((index > 0) && (heap.get(index) > heap.get(parent(index)))) {
swap(index, parent(index));
index = parent(index);
}
if (index != 0)
maxHeapify(index); // If it is little, push down
}
return heap.get(size);
}
public int maxLookUp() {
if (size == 0) {
return -1;
} else {
return heap.get(0);
}
}
public int extractMax() {
if (size == 0) return -1;
int min = heap.get(0);
heap.add(0, heap.get(size - 1));
size--;
maxHeapify(0);
return min;
}
public int getSize() {
return size;
}
private void swap(int firstIndex, int secondIndex) {
int temp = heap.get(firstIndex);
heap.add(firstIndex, heap.get(secondIndex));
heap.add(secondIndex, temp);
}
// test cases
public static void main(String[] args) {
int n;
Scanner sc = new Scanner(System.in);
MaxHeap maxHeap = new MaxHeap();
n = sc.nextInt();
String[] ins = new String[n];
sc.nextLine();
for(int i = 0; i < n; i++) {
ins[i] = sc.nextLine();
}
for(int i = 0; i < n; i++) {
String line = ins[i];
String[] inputs = line.split(" ");
if("size".equalsIgnoreCase(inputs[0])) {
System.out.println(maxHeap.getSize());
} else if("insert".equalsIgnoreCase(inputs[0])) {
maxHeap.insert(Integer.parseInt(inputs[1]));
} else if("delete".equalsIgnoreCase(inputs[0])) {
maxHeap.remove(Integer.parseInt(inputs[1]));
} else if("extractMax".equalsIgnoreCase(inputs[0])) {
maxHeap.extractMax();
} else if("maxLookup".equalsIgnoreCase(inputs[0])) {
System.out.println(maxHeap.maxLookUp());
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.