Thread: 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!

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);

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.

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.

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

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.

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?

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?

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.