I have ERROR with the HEAP to hold the tree. Could anyone scan the code and fix

Question

I have ERROR with the HEAP to hold the tree. Could anyone scan the code and fix it?

Thank you, very appreciated!!!

HERE IS THE CODE!!!!

import java.util.Scanner;

public class HuffmanEncoding {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("Enter a text: ");
String text = input.nextLine();
  
int[] counts = getCharacterFrequency(text); // Count frequency

System.out.printf("%-15s%-15s%-15s%-15s ",
"ASCII Code", "Character", "Frequency", "Code");
  
Tree tree = getHuffmanTree(counts); // Create a Huffman tree
String[] codes = getCode(tree.root); // Get codes
  
for (int i = 0; i < codes.length; i++)
if (counts[i] != 0) // (char)i is not in text if counts[i] is 0
System.out.printf("%-15d%-15s%-15d%-15s ",
i, (char)i + "", counts[i], codes[i]);
}
  
/** Get Huffman codes for the characters
* This method is called once after a Huffman tree is built
*/
public static String[] getCode(Tree.Node root) {
if (root == null) return null;
String[] codes = new String[2 * 128];
assignCode(root, codes);
return codes;
}
  
/* Recursively get codes to the leaf node */
private static void assignCode(Tree.Node root, String[] codes) {
if (root.left != null) {
root.left.code = root.code + "0";
assignCode(root.left, codes);
  
root.right.code = root.code + "1";
assignCode(root.right, codes);
}
else {
codes[(int)root.element] = root.code;
}
}
  
/** Get a Huffman tree from the codes */
public static Tree getHuffmanTree(int[] counts) {
// Create a heap to hold trees
Heap<Tree> heap = new Heap<Tree>(); // Defined in Listing 24.10
for (int i = 0; i < counts.length; i++) {
if (counts[i] > 0)
heap.add(new Tree(counts[i], (char)i)); // A leaf node tree
}
  
while (heap.getSize() > 1) {
Tree t1 = heap.remove(); // Remove the smallest weight tree
Tree t2 = heap.remove(); // Remove the next smallest weight
heap.add(new Tree(t1, t2)); // Combine two trees
}

return heap.remove(); // The final tree
}
  
/** Get the frequency of the characters */
public static int[] getCharacterFrequency(String text) {
int[] counts = new int[256]; // 256 ASCII characters
  
for (int i = 0; i < text.length(); i++)
counts[(int)text.charAt(i)]++; // Count the character in text
  
return counts;
}
  
/** Define a Huffman coding tree */
public static class Tree implements Comparable<Tree> {
Node root; // The root of the tree

/** Create a tree with two subtrees */
public Tree(Tree t1, Tree t2) {
root = new Node();
root.left = t1.root;
root.right = t2.root;
root.weight = t1.root.weight + t2.root.weight;
}
  
/** Create a tree containing a leaf node */
public Tree(int weight, char element) {
root = new Node(weight, element);
}
  
@Override /** Compare trees based on their weights */
public int compareTo(Tree t) {
if (root.weight < t.root.weight) // Purposely reverse the order
return 1;
else if (root.weight == t.root.weight)
return 0;
else
return -1;
}

public class Node {
char element; // Stores the character for a leaf node
int weight; // weight of the subtree rooted at this node
Node left; // Reference to the left subtree
Node right; // Reference to the right subtree
String code = ""; // The code of this node from the root

/** Create an empty node */
public Node() {
}
  
/** Create a node with the specified weight and character */
public Node(int weight, char element) {
this.weight = weight;
this.element = element;
}
}
}
}

Explanation / Answer

import java.io.*;

import java.util.Scanner;
import javax.swing.*;
import java.awt.*;
import java.util.*;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
public class HuffmanEncoding {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("Enter a text: ");
String text = input.nextLine();
int[] counts = getCharacterFrequency(text); // Count frequency
System.out.printf("%-15s%-15s%-15s%-15s ",
"ASCII Code", "Character", "Frequency", "Code");
Tree tree = getHuffmanTree(counts); // Create a Huffman tree
String[] codes = getCode(tree.root); // Get codes
for (int i = 0; i < codes.length; i++) {
if (counts[i] != 0) // (char)i is not in text if counts[i] is 0
{
System.out.printf("%-15d%-15s%-15d%-15s ",
i, (char) i + "", counts[i], codes[i]);
}
}
}
/**
* Get Huffman codes for the characters
*
* This method is called once after a Huffman tree is built
*
*/
public static String[] getCode(Tree.Node root) {
if (root == null) {
return null;
}
String[] codes = new String[2 * 128];
assignCode(root, codes);
return codes;
}
/* Recursively get codes to the leaf node */
private static void assignCode(Tree.Node root, String[] codes) {
if (root.left != null) {
root.left.code = root.code + "0";
assignCode(root.left, codes);
root.right.code = root.code + "1";
assignCode(root.right, codes);
} else {
codes[(int) root.element] = root.code;
}
}
/**
* Get a Huffman tree from the codes
*/
public static Tree getHuffmanTree(int[] counts) {
// Create a heap to hold trees
Heap<Tree> heap = new Heap<Tree>(); // Defined in Listing 24.10
for (int i = 0; i < counts.length; i++) {
if (counts[i] > 0) {
heap.add(new Tree(counts[i], (char) i)); // A leaf node tree
}
}
while (heap.sz() > 1) {
Tree t1 = heap.remove(); // Remove the smallest weight tree
Tree t2 = heap.remove(); // Remove the next smallest weight
heap.add(new Tree(t1, t2)); // Combine two trees
}
return heap.remove(); // The final tree
}
/**
* Get the frequency of the characters
*/
public static int[] getCharacterFrequency(String text) {
int[] counts = new int[256]; // 256 ASCII characters
for (int i = 0; i < text.length(); i++) {
counts[(int) text.charAt(i)]++; // Count the character in text
}
return counts;
}
/**
* Define a Huffman coding tree
*/
public static class Tree implements Comparable<Tree> {
Node root; // The root of the tree
/**
* Create a tree with two subtrees
*/
public Tree(Tree t1, Tree t2) {
root = new Node();
root.left = t1.root;
root.right = t2.root;
root.weight = t1.root.weight + t2.root.weight;
}
/**
* Create a tree containing a leaf node
*/
public Tree(int weight, char element) {
root = new Node(weight, element);
}
@Override
/**
* Compare trees based on their weights
*/
public int compareTo(Tree t) {
if (root.weight < t.root.weight) // Purposely reverse the order
{
return 1;
} else if (root.weight == t.root.weight) {
return 0;
} else {
return -1;
}
}
public class Node {
char element; // Stores the character for a leaf node
int weight; // weight of the subtree rooted at this node
Node left; // Reference to the left subtree
Node right; // Reference to the right subtree
String code = ""; // The code of this node from the root
/**
* Create an empty node
*/
public Node() {
}
/**
* Create a node with the specified weight and character
*/
public Node(int weight, char element) {
this.weight = weight;
this.element = element;
}
}
}
static class Heap<E extends Comparable<E>> {
private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
public Heap() {
}
public Heap(E[] objects) {
for (int i = 0; i < objects.length; i++) {
add(objects[i]);
}
}
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;
}
}
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;
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;
}
}
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;
}
public int sz() {
return list.size();
}
}
}

__________________________________________________________________________________

output:

Enter a text: hello world
ASCII Code Character Frequency Code   
32 1 1100   
100 d 1 1111   
101 e 1 011
104 h 1 010
108 l 3 10   
111 o 2 00   
114 r 1 1110   
119 w 1 1101   

_______________________________________________________________________________________

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.