Skip to Main Content

Java Programming

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

need help - convert a list into minheap - tree where parent is smaller

807580Nov 24 2009 — edited Nov 24 2009
in the following code I am able to read a file and do character frequency using another class that I have and at this point I have a sorted collection of linked lists. now what I have to do is insert the sorted collection into minheap - in minheap each parent is less than its children.

so lets say my input string to the program is abbcccdddd
here a will be the root since its frequency is the lowest of. and b and c will be its two children. d can go under b or c as long as b or c are less than frequency of d.


here is what I have so far.
import java.io.*;
import java.util.*;

public class Huffman {

	public static void main(String[] args) {
		if ( args.length != 1 ) {
			System.err.println( "Usage: Huffman filename" );
			System.exit( 0 );
		}

		List characters = new ArrayList();
		int currentChar;

		System.out.println( "Beginning Encoding" );

		try {
			BufferedReader input = new BufferedReader( new FileReader( args[ 0 ] ) );

			System.out.println( "=Generating Frequency Table" );

			currentChar = input.read();

			// Initialize Array List ( oly 256 valid ASCII characters )
			for ( int i = 0; i < 256; i++ ) {
				characters.add( new HuffmanCharacter( ( char ) i ) );
			}

			// Read in a char at a time while there still are chars
			while( currentChar != -1 ) {
				if ( currentChar < 0 || currentChar > 255 ) {
					System.err.println( "Huffman: File contains non-ASCII characters.  Can not compress." );
					System.exit( 0 );
				}
				HuffmanCharacter theCharacter = ( HuffmanCharacter ) characters.get( currentChar );
				theCharacter.incrementFrequency();
				currentChar = input.read();
			}

			input.close();
		} catch( FileNotFoundException e ) {
			System.err.println( "Huffman: " + args[ 0 ] + " could not be found" );
			System.exit( 0 );
		} catch( IOException e ) {
			System.err.println( "Huffman: IO Error" );
			System.exit( 0 );
		}

		System.out.println( "=Creating Tree of Character Frequencies" );
		System.out.println( "==Creating Nodes" );

		List usedChars = new LinkedList();
		List usedNodes = new LinkedList();
		List allNonNullNodes = new LinkedList();

		// Trim zero frequency characters
		for ( int i = 0; i < characters.size(); i++ ) {
			HuffmanCharacter aCharacter = ( HuffmanCharacter ) characters.get( i );
			if ( aCharacter.getFrequency() > 0 ) {
				usedChars.add( aCharacter );
			}
		}

		for ( int i = 0; i < usedChars.size(); i++ ) {
			HuffmanTreeNode aNode = new HuffmanTreeNode( (HuffmanCharacter) usedChars.get( i ) );
			usedNodes.add( aNode );
			allNonNullNodes.add( aNode );
		}

		System.out.println( "===Nodes: " + usedNodes );
		System.out.println( "==Connecting Nodes" );
		System.out.println( "===Total Unique Characters in file: " + usedNodes.size() );

		if ( usedNodes.size() == 0 ) {
			System.err.println( "===No Nodes to connect" );
			System.err.println( "===Error Encoding...Exiting" );
			System.exit( 0 );
		}

		Collections.sort( usedNodes );
		System.out.println(usedNodes);

	}


}
NEED HELP.... THANKS
Comments
Locked Post
New comments cannot be posted to this locked post.
Post Details
Locked on Dec 22 2009
Added on Nov 24 2009
1 comment
131 views