Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 10 of 10

Thread: generate priority queue from hashmap help

  1. #1
    Junior Member
    Join Date
    May 2011
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default generate priority queue from hashmap help

    Hey guys I'm new here and was came here hoping to find an answer to my problem. I've never used priority queues before so I'm not sure I'm doing it right but here it goes...

    I'm trying to create a huffman encoding / decoding program but I'm running into some issues. The encoding or decoding i'll tackle when i get there but i have a good grasp on that part anyways...

    I need help turning my hashmap, which holds the character and the number of occurrences of it, and putting it into a priority queue. I have never used hashmaps or pqs before so i'm a little stumped.

    import java.util.HashMap;
    import java.io.*;
    import java.util.Scanner;
    import java.util.Iterator;
    import java.lang.StringBuffer;
    import java.util.PriorityQueue;
     
    public class Huffman{
     
    	public static void main (String []args) throws Exception{
     
    		HashMap <Character, Integer> hm = new HashMap<Character, Integer>();
    		File file = new File("file.txt");
    		Scanner finput = new Scanner(file);
    		StringBuffer text = new StringBuffer("");
    		PriorityQueue pq = new PriorityQueue();		
    		while (finput.hasNext()){
    			String s = finput.next();
    			char [] chars = s.toCharArray();
    			for(int i=0; i < chars.length; i++){
    				char c = chars[i];
    				if (hm.containsKey(c)){
    					int freq = hm.get(c);
    					hm.put(c, freq+1);
    				}
    				else{hm.put(c, 1);}
    			}
    		}
     
    		System.out.println("Hashmap!");
    		System.out.println(hm);
     
    		Iterator it = hm.keySet().iterator();
     
    		while(it.hasNext()){
    			pq.add(it.next());
    		}
     
    		System.out.println("Priority Queue!");
    		while(pq.size() > 0){
    		       System.out.println(pq.remove());
     
    		}
     
    	}
    }
     
    class Node implements Comparable<Node> {
        private final char ch;
        private final int freq;
        private final Node left, right;
     
        Node(char ch, int freq, Node left, Node right) {
            this.ch    = ch;
            this.freq  = freq;
            this.left  = left;
            this.right = right;
        }
     
     
        private boolean isLeaf() {
            assert (left == null && right == null) || (left != null && right != null);
            return (left == null && right == null);
        }
     
     
        public int compareTo(Node that) {
            return this.freq - that.freq;
        }
    }

    It outputs...
    Hashmap!
    {f=2, g=3, e=10, b=1, c=1, a=3, n=1, o=4, l=3, k=1, h=3, i=6, t=5, s=6, r=2, p=3, y=1, x=1}
    Priority Queue!
    a
    b
    c
    e
    f
    g
    h
    i
    k
    l
    n
    o
    p
    r
    s
    t
    x
    y

    This is my text file... Though it doesn't matter what you use my program still isn't correct.

    this is a text file go go gooberry
    please keep the spaces in this file

    My priority queue should have the char with the highest frequency displayed first but it only shows chars anyways, how do i get it to show chars and frequencies also while putting them into the correct order?

    Thanks guys!


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,186
    Thanks
    49
    Thanked 2,172 Times in 2,145 Posts

    Default Re: generate priority queue from hashmap help

    Can you show what the correct output would be for your input file?

    To make your code easier to test, I changed it thus:
            String Input = "this is a text file go go gooberry\nplease keep the spaces in this file";
    	Scanner finput = new Scanner(Input);

  3. The Following User Says Thank You to Norm For This Useful Post:

    Scotty33 (May 23rd, 2011)

  4. #3
    Junior Member
    Join Date
    May 2011
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: generate priority queue from hashmap help

    Well I need to see the priority queue print out in the correct order... If my understanding of PQ's is correct then it should either print out smallest to largest or largest to smallest but mine does neither... If you look at what my hashmap prints out the the number with the highest frequency is e with 10 and the lowest are b,c,n,k,y,z with one. So I'm assuming either e should be the first or last number removed from the PQ and the b,c,n,k,y,x should be the opposite of e. Instead I'm getting them printed out in alphabetical order (which makes sense but its not what I need) when it should print out in order of numbers with the highest frequency.

    Any other explanation needed please guide me into what you need to help me, I really appreciate it.

  5. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,186
    Thanks
    49
    Thanked 2,172 Times in 2,145 Posts

    Default Re: generate priority queue from hashmap help

    Where do you use the Node class?
    What type of object is added to the PriorityQueue object?

    What should the output look like? Now its a list of the letters of the alphabet.
    Last edited by Norm; May 23rd, 2011 at 04:04 PM.

  6. #5
    Junior Member
    Join Date
    May 2011
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: generate priority queue from hashmap help

    I didn't my friend just pointed that out...
    So I changed where I created my PQ to...

    PriorityQueue<Node> pq= new PriorityQueue<Node>();

    Also he suggested I change my compareTo class to

    public int compareTo(Node that) {
        	if(this.freq < that.freq){
        	return -1;
        	}
        	else if(this.freq == that.freq){
        	return 0;
        	}
        	else return 1;
        }

    The node should contain the Character and its frequency and when it creates the list it should create it with the node with the highest frequency on top and the lowest frequency on the bottom.

    The output should be just like the hashmap just ordered from greatest to smallest frequencies.

  7. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,186
    Thanks
    49
    Thanked 2,172 Times in 2,145 Posts

    Default Re: generate priority queue from hashmap help

    And what about the first two questions:
    Where do you use the Node class?
    What type of object is added to the PriorityQueue object?

  8. #7
    Junior Member
    Join Date
    May 2011
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: generate priority queue from hashmap help

    The node class is used to generate a priority queue of nodes (if my understanding of nodes is correct), each node is suppose to contain the character and its frequency. The node is then added to the priority queue.

    The priority queue is suppose to arrange by frequencies though, not the characters.

    If my understanding of nodes or priority queues are that far off I'm sorry, I hope I'm not frustrating you too much with my issues.

  9. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,186
    Thanks
    49
    Thanked 2,172 Times in 2,145 Posts

    Default Re: generate priority queue from hashmap help

    Where do you use the Node class?

    By use I mean something like this:
    Node aNode = new Node(.....); // create a node
    // then do something with aNode

    What do you put in the PriorityQueue?

  10. #9
    Junior Member
    Join Date
    May 2011
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: generate priority queue from hashmap help

    I guess I don't use the node class currently and what im thinking is wrong now is that i should be creating nodes with the char and frequency then put the nodes into the priority queue.

    Does that sound like the right track?
    And if so how would i make it so the priority queue puts the nodes in by frequency and not character?

  11. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,186
    Thanks
    49
    Thanked 2,172 Times in 2,145 Posts

    Default Re: generate priority queue from hashmap help

    Yes that approach sounds right.
    Who wrote the code for the Node class with its compareTo method?

    You should read the API doc for the PriorityQueue class to see how it orders its contents.

Similar Threads

  1. Implementing a priority queue using a max heap
    By jsinclair1482 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: April 15th, 2011, 11:56 AM
  2. Priority Queue using comparable
    By jkalm in forum Collections and Generics
    Replies: 6
    Last Post: December 5th, 2010, 09:02 PM
  3. Replies: 4
    Last Post: July 21st, 2010, 04:07 PM
  4. How do I fix my program so I can use the keyboard to type in the numbers?
    By rocafella5007 in forum File I/O & Other I/O Streams
    Replies: 1
    Last Post: April 29th, 2009, 02:39 PM