In Java, implement a heap class that is generic. The main important part of this
ID: 3914748 • 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.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.NoSuchElementException;
public class Heap<E extends Comparable<E>> {
/** The number of children each node has *. */
private static final int d = 2;
/** The size. */
private int size;
/** The data heap. */
private Object[] dataHeap;
/** The capacity. */
private int capacity = 100;
/** The traversed data heap. */
private Object[] traversedDataHeap;
/**
* Instantiates a new heap.
*/
public Heap() {
size = 0;
dataHeap = new Object[capacity + 1];
Arrays.fill(dataHeap, -1);
}
/**
* Function to check if heap is empty *.
*
* @return true, if is empty
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Check if heap is full *.
*
* @return true, if is full
*/
public boolean isFull() {
return size == dataHeap.length;
}
/**
* Function to insert element.
*
* @param x the x
*/
public void add(E x) {
if (isFull())
growHeapSize();
/** Percolate up **/
dataHeap[size++] = x;
heapifyUp(size - 1);
}
/**
* Function to delete element at an index *.
*
* @param ind the ind
* @return the e
*/
@SuppressWarnings("unchecked")
public E delete(int ind) {
if (isEmpty())
throw new NoSuchElementException("Heap Underflow Exception");
E keyItem = (E) dataHeap[ind];
dataHeap[ind] = dataHeap[size - 1];
size--;
heapifyDown(ind);
return keyItem;
}
/**
* Delete.
*
* @param value the value
*/
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");
}
}
}
/**
* Find.
*
* @param value the value
* @return the string
*/
public String find(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();
}
/**
* Gets the data occurence.
*
* @return the data occurence
*/
@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;
}
/**
* Traverse heap.
*/
public void traverseHeap() {
if (traversedDataHeap == null) {
traversedDataHeap = new Object[dataHeap.length];
System.arraycopy(dataHeap, 0, traversedDataHeap, 0, traversedDataHeap.length);
}
preOrder(0);
printHeap(traversedDataHeap);
}
/**
* Pre order.
*
* @param index the index
*/
public void preOrder(int index) {
if (index >= size) {
return;
}
System.out.println(traversedDataHeap[index]);
preOrder((2 * index) + 1);
preOrder((2 * index) + 2);
}
/**
* Function heapifyUp *.
*
* @param childInd the child ind
*/
@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;
}
/**
* Function heapifyDown *.
*
* @param ind the ind
*/
@SuppressWarnings("unchecked")
private void heapifyDown(int ind) {
int child;
E tmp = (E) dataHeap[ind];
while (kthChild(ind, 1) < size) {
child = minmumChild(ind);
E parent = (E) dataHeap[child];
if (parent.compareTo(tmp) == -1)
dataHeap[ind] = dataHeap[child];
else
break;
ind = child;
}
dataHeap[ind] = tmp;
}
/**
* Function to get smallest child *.
*
* @param ind the ind
* @return the int
*/
@SuppressWarnings("unchecked")
private int minmumChild(int ind) {
int bestChild = kthChild(ind, 1);
int k = 2;
int pos = kthChild(ind, k);
while ((k <= d) && (pos < size)) {
E node1 = (E) dataHeap[pos];
E node2 = (E) dataHeap[bestChild];
if (node1.compareTo(node2) == -1)
bestChild = pos;
pos = kthChild(ind, k++);
}
return bestChild;
}
/**
* Function to get index parent of i *.
*
* @param i the i
* @return the int
*/
private int parent(int i) {
return (i - 1) / d;
}
/**
* Function to get index of k th child of i *.
*
* @param i the i
* @param k the k
* @return the int
*/
private int kthChild(int i, int k) {
return d * i + k;
}
/**
* Grow heap size.
*/
private void growHeapSize() {
int newSize = capacity / 2;
Object[] newDataHeap = new Object[newSize];
System.arraycopy(dataHeap, 0, newDataHeap, 0, newSize);
dataHeap = newDataHeap;
}
/**
* Function to print heap *.
*
* @param heap the heap
*/
public void printHeap(Object[] heap) {
System.out.print(" Heap = ");
for (int i = 0; i < size; i++)
System.out.print(heap[i] + " ");
System.out.println();
}
}
==============================HeapManager.java============================
package heap_impl;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
public class HeapManager {
/** The scan. */
private static Scanner scan = new Scanner(System.in);
/**
* The main method.
*
* @param args the arguments
*/
public static void main(String[] args) {
boolean stopFlag = false;
Heap<String> wordHeap = new Heap<>();
do {
System.out.println("Select any option: 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);
}
/**
* Perform operations.
*
* @param selection the selection
* @param stopFlag the stop flag
* @param wordHeap the word heap
* @return true, if successful
*/
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.find(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:
writeIntoOutputFile(wordHeap);
stopFlag = true;
break;
}
return stopFlag;
}
/**
* Write into output file.
*
* @param wordHeap the word heap
*/
private static void writeIntoOutputFile(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 occured during reading file......");
}
finally {
if (fw != null && bw != null) {
try {
fw.close();
bw.close();
}
catch (IOException e) {
System.err.println("Error occured during closing file reader......");
}
}
}
}
/**
* Read file.
*
* @param fileName the file name
* @param wordHeap the word heap
*/
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 available. Please try again.....");
}
catch (IOException e) {
System.err.println("Error occured during reading file......");
}
finally {
if (fr != null && br != null) {
try {
fr.close();
br.close();
}
catch (IOException e) {
System.err.println("Error occured during closing file reader......");
}
}
}
}
}
==================================words.txt==============================================
Mercury
Venus
Earth
Mars
Jupiter
Saturn
Uranus
Neptune0
Pluto
Jupiter
Saturn
Uranus
Neptune0
Pluto
Uranus
Neptune0
Pluto
============================Output.txt================================
Earth - 0
Jupiter - 1
Mars - 0
Mercury - 0
Neptune0 - 2
Pluto - 2
Saturn - 1
Uranus - 2
Venus - 0
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.