Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Below is a picture of the increase and decrease keys from the notes Heres the Main template: import java.util.Scanner; public class Main { public static
Below is a picture of the increase and decrease keys from the notes
Heres the Main template:
import java.util.Scanner; public class Main { public static final char WALL = '@'; public static final char INFO = '*'; public static final char HERO = ';'; public static final int SLEEP = 0; public static boolean mhw; public static int heroRow; public static int heroCol; public static int infoRow; public static int infoCol; public static int info2Row; public static int info2Col; public static boolean quit; public static Scanner scanner; public static char[][] map; public static boolean smh; public static boolean ihw; public static void main(String[] args) throws InterruptedException { // initialize map and hero coordinates map = new char[8][10*2]; heroRow = 6; heroCol = 1; infoRow = 1; infoCol = 9; info2Row = 6; info2Col = 17; smh = false; mhw = true; ihw = true; quit = false; scanner = new Scanner(System.in); while (!quit) { clearScreen(); draw(); System.out.println(); if (!smh && (heroRow == infoRow && heroCol == infoCol)) { smh = true; } else { menu(); } } } private static void clearScreen() { // UNIX based systems System.out.print("\033[H\033[2J"); // WINDOWS based systems try { new ProcessBuilder("cmd", "/c", "cls").inheritIO().start().waitFor(); } catch(Exception e) { // couldn't clear, oh well } // clear map too for(int r = 0; r = 0) { mapChar = map[heroRow-1][heroCol]; if (mapChar == ' ' || mapChar == INFO) { heroRow--; } } break; // go left case 'a': if (heroCol-1 >= 0) { mapChar = map[heroRow][heroCol-1]; if (mapChar == ' ' || mapChar == INFO) { heroCol--; } } break; // go down case 's': if (heroRow+1Heres the MaxHeap template:
public class MaxHeap { private int[] data; private int size; // constructor public MaxHeap(){ size = 0; data = new int[7]; } /** Insert operation: It inserts a given key into the MaxHeap */ public void insert(int key){ if(isEmpty()){ data[0] = key; size++; } else { data[size] = key; size++; maxHeapifyUp(); } } /** findMax operation: It returns top node if the heap is not empty */ public int findMax(){ if(isEmpty()){ return -1; } return data[0]; } /** extract Max operation: It returns max node and re-sorts heap to new correct order */ public int extractMax(){ if(isEmpty()){ return -1; } // swap top node with last node int val = data[0]; int temp = data[0]; data[0] = data[size-1]; data[size-1] = temp; size--; maxHeapifyDown(); return val; } /** maxHeapifyUp operation: It fixes violations of max heap */ private void maxHeapifyUp(){ int index = size - 1; while(index > 0){ if(data[(int)(index-1)/2]Heres the MinHeap template:
public class MinHeap { private int[] data; private int size; // constructor public MinHeap(){ data = new int[7]; size = 0; } /** insert(key) operation: It inserts a given key into the MaxHeap */ public void insert(int key){ if(isEmpty()){ data[0] = key; size++; } else { data[size] = key; size++; minHeapifyUp(); } } /** findMin operation: It returns top node if the heap is not empty */ public int findMin(){ if(isEmpty()){ return -1; } return data[0]; } /** extractMin opeartion: It returns min node and re-sorts heap to new correct order */ public int extractMin(){ if(isEmpty()){ return -1; } // swap top node with last node int val = data[0]; int temp = data[0]; data[0] = data[size-1]; data[size-1] = temp; size--; minHeapifyDown(); return val; } /** minHeapifyUp opeartion: It fixes violations of min heap */ private void minHeapifyUp(){ int index = size - 1; while(index > 0){ if(data[(int)(index-1)/2] > data[index]){ // swap nodes int temp = data[(int)(index-1)/2]; data[(int)(index-1)/2] = data[index]; data[index] = temp; } index--; } } /** minHeapifyDown opeartion: It fixes violations of min heap */ private void minHeapifyDown(){ int index = 0; while(index data[2*index+1]){ // swap nodes int temp = data[index]; data[index] = data[2*index+1]; data[2*index+1] = temp; } if(data[index] > data[2*index+2]){ // swap nodes int temp = data[index]; data[index] = data[2*index+2]; data[2*index+2] = temp; } index++; } } /** isEmpty operation: It returns true if empty */ public boolean isEmpty(){ return size == 0; } }to overload the minHeapifyDown and minHeapifyUp functions to include a parameter for position. In other words, in addition to: private void minHeapifyUp() {} private void minHeapifyDown( {} You will need to also include (not modify but include in addition to) the following functions: private void minHeapifyUp(int position) {} private void minHeapifyDown(int position) {} process will take place starting at the node. Again I want to clarify that you are not modifying the existing functions, but instead adding two new functions of the same name. To test these new functions out, put the following code into a new file called Bonus.java: public class Bonus \{ public static void main(String[] args) \{ MinHeap heap = new MinHeap () ; heap.insert(8); heap.insert (1); heap.insert(6); heap.insert (3); heap.decreaseKey (4,0); heap.increaseKey (0,9); heap.decreaseKey (2,5); heap.decreaseKey (2,0); heap.increaseKey (1,11); System.out. print("Numbers in sorted order: "); while(!heap.isEmpty()) \{ System.out.print(heap.extractMin() + " "); System.out.println(); \} Is it a max heap again? Yep! If there were more levels we would recursively call maxHeapifyDown until we finally reached the bottom of the heap or until the max heap property is no longer violated. So, to be clear, maxHeapifyDown goes from root to leaf whereas maxHeapifyUp goes from leaf to root. There are two other functions we could implement with our max heap: increaseKey (pos, newKey) Changes the key of the node at position pos with the value of newKey. New key must be higher than the current key in that node. decreaseKey (pos, newKey) Changes the key of the node at position pos with the value of newKey. New key must be lower than the current key in that node. You should be able to figure out how to implement these. For increaseKey we simply change node's key at the given position to the new key value and then call maxHeapifyUp on that changed node. We call maxHeapifyU since we are increasing the node's key, so this potentially can move that node up the tree. For decreaseKey w would call maxHeapifyDown on the node after changing its key, since this could potentially move that node down the tree. But how do we know which node is at the position given by pos? To answer this question we must look at how we can implement this max heap data type. Your knee jerk reaction is probably to use something similar to the nodes of a binary tree. After all, a heap is a binary tree. You are probably thinking something along the lines of this: public class Node \{ to overload the minHeapifyDown and minHeapifyUp functions to include a parameter for position. In other words, in addition to: private void minHeapifyUp() {} private void minHeapifyDown( {} You will need to also include (not modify but include in addition to) the following functions: private void minHeapifyUp(int position) {} private void minHeapifyDown(int position) {} process will take place starting at the node. Again I want to clarify that you are not modifying the existing functions, but instead adding two new functions of the same name. To test these new functions out, put the following code into a new file called Bonus.java: public class Bonus \{ public static void main(String[] args) \{ MinHeap heap = new MinHeap () ; heap.insert(8); heap.insert (1); heap.insert(6); heap.insert (3); heap.decreaseKey (4,0); heap.increaseKey (0,9); heap.decreaseKey (2,5); heap.decreaseKey (2,0); heap.increaseKey (1,11); System.out. print("Numbers in sorted order: "); while(!heap.isEmpty()) \{ System.out.print(heap.extractMin() + " "); System.out.println(); \} Is it a max heap again? Yep! If there were more levels we would recursively call maxHeapifyDown until we finally reached the bottom of the heap or until the max heap property is no longer violated. So, to be clear, maxHeapifyDown goes from root to leaf whereas maxHeapifyUp goes from leaf to root. There are two other functions we could implement with our max heap: increaseKey (pos, newKey) Changes the key of the node at position pos with the value of newKey. New key must be higher than the current key in that node. decreaseKey (pos, newKey) Changes the key of the node at position pos with the value of newKey. New key must be lower than the current key in that node. You should be able to figure out how to implement these. For increaseKey we simply change node's key at the given position to the new key value and then call maxHeapifyUp on that changed node. We call maxHeapifyU since we are increasing the node's key, so this potentially can move that node up the tree. For decreaseKey w would call maxHeapifyDown on the node after changing its key, since this could potentially move that node down the tree. But how do we know which node is at the position given by pos? To answer this question we must look at how we can implement this max heap data type. Your knee jerk reaction is probably to use something similar to the nodes of a binary tree. After all, a heap is a binary tree. You are probably thinking something along the lines of this: public class Node \{
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started