In Java, implement a heap class that is generic. The main important part of this
ID: 3914765 • Letter: I
Question
In Java, implement a heap class that is generic. The main important part of this heap is the following:
a) The heap will allow for the storing of multiples of the same value.
b) The heap will be a min-heap, which means minimum will be at the top.
The heap itself should contain the following:
-an array based implementation including a way to keep track of any duplicates that are added to the heap
-appropriate constructors
-add and remove methods for individual nodes in the heap
-a method to return the number of occurrences of particular data element
-any other helper methods or methods required to complete the task described below
The task follows:
Write a GUI TESTER class that allows users to enter words one at a time or to read from a file. These processes should not be mutually exclusive, meaning that a user could do both – read from a file and then add more words. The GUI should also allow a user to search for a word (and report it’s presence and the number of occurrences), delete a word (one occurrence or all occurrences at once) and traverse the heap one element at a time using a pre-order traversal. There should also be a mechanism to output the heap to a new output file. The output file contains word-number pairs which indicate the word and the number of occurrences in alphabetical order. (Hint: Make a copy of the heap and destroy it one element at a time, knowing that the smallest element is always at the top.)
***Please ensure you create a GUI class.
Explanation / Answer
//Program
//Heap.java
package heap_impl;
import java.util.HashMap;
import java.util.Arrays;
import java.util.Map;
import java.util.NoSuchElementException;
public class Heap<E extends Comparable<E>> {
private static final int d = 2;
private int syz;//size
private Object[] dataHeap;
private int capcity = 100;
private Object[] traversedDataHeap;
public Heap() {
syz = 0;
dataHeap = new Object[capcity + 1];
Arrays.fill(dataHeap, -1);
}
public boolean sEmpty() {
return syz == 0;
}
public boolean sFull() {
return syz == dataHeap.length;
}
public void add(E x) {
if (sFull())
growHeapSize();
dataHeap[syz++] = x;
heapifyUp(syz - 1);
}
@SuppressWarnings("unchecked")
public E delete(int ind) {
if (sEmpty())
throw new NoSuchElementException("Heap Underflow Exception");
E keyItem = (E) dataHeap[ind];
dataHeap[ind] = dataHeap[syz - 1];
syz--;
heapifyDown(ind);
return keyItem;
}
public void delete(E value) {
for (int i = 0; i < dataHeap.length; i++) {
if (dataHeap[i].equals(value)) {
System.out.println(delete(i) + " deleted successfully");
}
}
}
public String finding(E value) {
Map<E, Integer> map = new HashMap<>();
int count = 1;
for (int i = 0; i < dataHeap.length; i++) {
if (dataHeap[i].equals(value)) {
map.put(value, count++);
}
}
if (map.get(value) == null || map.get(value).equals(0)) {
System.err.println("No result found.......");
}
return map.toString();
}
@SuppressWarnings("unchecked")
public Map<E, Integer> getDataOccurence() {
Map<E, Integer> map = new HashMap<>();
for (Object value : dataHeap) {
if (!value.equals(-1)) {
if (map.get(value) == null) {
map.put((E) value, 0);
}
else {
map.put((E) value, map.get(value) + 1);
}
}
}
return map;
}
public void traverseHeap() {
if (traversedDataHeap == null) {
traversedDataHeap = new Object[dataHeap.length];
System.arraycopy(dataHeap, 0, traversedDataHeap, 0, traversedDataHeap.length);
}
preOrder(0);
printHeap(traversedDataHeap);
}
public void preOrder(int index) {
if (index >= syz) {
return;
}
System.out.println(traversedDataHeap[index]);
preOrder((2 * index) + 1);
preOrder((2 * index) + 2);
}
@SuppressWarnings("unchecked")
private void heapifyUp(int childInd) {
E tmp = (E) dataHeap[childInd];
E parent = (E) dataHeap[parent(childInd)];
while (childInd > 0 && tmp.compareTo(parent) == -1) {
dataHeap[childInd] = dataHeap[parent(childInd)];
childInd = parent(childInd);
}
dataHeap[childInd] = tmp;
}
@SuppressWarnings("unchecked")
private void heapifyDown(int ind) {
int child;
E tmp = (E) dataHeap[ind];
while (kthChild(ind, 1) < syz) {
child = minmumChild(ind);
E parent = (E) dataHeap[child];
if (parent.compareTo(tmp) == -1)
dataHeap[ind] = dataHeap[child];
else
break;
ind = child;
}
dataHeap[ind] = tmp;
}
@SuppressWarnings("unchecked")
private int minmumChild(int ind) {
int bestChild = kthChild(ind, 1);
int k = 2;
int pos = kthChild(ind, k);
while ((k <= d) && (pos < syz)) {
E node1 = (E) dataHeap[pos];
E node2 = (E) dataHeap[bestChild];
if (node1.compareTo(node2) == -1)
bestChild = pos;
pos = kthChild(ind, k++);
}
return bestChild;
}
private int parent(int i) {
return (i - 1) / d;
}
private int kthChild(int i, int k) {
return d * i + k;
}
private void growHeapSize() {
int newSize = capcity / 2;
Object[] newDataHeap = new Object[newSize];
System.arraycopy(dataHeap, 0, newDataHeap, 0, newSize);
dataHeap = newDataHeap;
}
public void printHeap(Object[] heap) {
System.out.print(" Heap = ");
for (int i = 0; i < syz; i++)
System.out.print(heap[i] + " ");
System.out.println();
}
}
==============================HeapManager.java============================
package heap_impl;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.FileWriter;
import java.util.Scanner;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.util.ArrayList;
import java.io.FileNotFoundException;
import java.util.List;
import java.util.Collections;
import java.util.Map;
public class HeapManager {
private static Scanner scan = new Scanner(System.in);
public static void main(String[] args) {
boolean stopFlag = false;
Heap<String> wordHeap = new Heap<>();
do {
System.out.println("Select any from List: 1.Add words from file. 2.Add word maually. 3.Search a word. 4.Delete word. 5.Traverse the words. 6.Exit");
int selection = scan.nextInt();
stopFlag = performOperations(selection, stopFlag, wordHeap);
} while (!stopFlag);
}
private static boolean performOperations(int selection, Boolean stopFlag, Heap<String> wordHeap) {
switch (selection) {
case 1:
System.out.println("Enter file name: ");
String fileName = scan.next();
readFile(fileName, wordHeap);
break;
case 2:
System.out.println("Enter word: ");
String word = scan.next();
wordHeap.add(word);
break;
case 3:
System.out.println("Enter the word to be searched: ");
String searchKey = scan.next();
System.out.println(wordHeap.finding(searchKey));
break;
case 4:
System.out.println("Enter the word to be deleted:");
String wordToBeDeleted = scan.next();
wordHeap.delete(wordToBeDeleted);
break;
case 5:
wordHeap.traverseHeap();
return stopFlag;
case 6:
writetoOutputFile(wordHeap);
stopFlag = true;
break;
}
return stopFlag;
}
private static void writetoOutputFile(Heap<String> wordHeap) {
FileWriter fw = null;
BufferedWriter bw = null;
try {
Map<String, Integer> map = wordHeap.getDataOccurence();
fw = new FileWriter("outputFile.txt");
bw = new BufferedWriter(fw);
List<String> keys = new ArrayList<>();
for (String key : map.keySet()) {
keys.add(key);
}
Collections.sort(keys);
for (String val : keys) {
String text = String.format("%s - %d ", val, map.get(val));
bw.write(text);
}
bw.flush();
}
catch (IOException e) {
System.err.println("Error: reading file not found......");
}
finally {
if (fw != null && bw != null) {
try {
fw.close();
bw.close();
}
catch (IOException e) {
System.err.println("Error: file closing problem found......");
}
}
}
}
private static void readFile(String fileName, Heap<String> wordHeap) {
FileReader fr = null;
BufferedReader br = null;
try {
fr = new FileReader(fileName);
br = new BufferedReader(fr);
String line = null;
while ((line = br.readLine()) != null) {
wordHeap.add(line);
}
}
catch (FileNotFoundException e) {
System.err.println("File is not found. Please try again.....");
}
catch (IOException e) {
System.err.println("Error: reading time file isuee......");
}
finally {
if (fr != null && br != null) {
try {
fr.close();
br.close();
}
catch (IOException e) {
System.err.println("Error: File closing problem found......");
}
}
}
}
}
++++++++++++++++++++++++++++++++++++++++++++words.txt++++++++++++++++++++++++++++++++++++++
Mercury
Venus
Earth
Mars
Jupiter
Saturn
Uranus
Neptune0
Pluto
Jupiter
Saturn
Uranus
Neptune0
Pluto
Uranus
Neptune0
Pluto
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.