1

Here is the code...

public class Huffman_Coding {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a string to compress: ");
        String str = sc.nextLine();
        sc.close();
        HashString hs = new HashString();

        HashMap<Character, Integer> hm = hs.getStringHash(str);

        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        for (char ch : hm.keySet()) {
            pq.add(new Node(null, null, hm.get(ch), ch));
        }
        System.out.println(pq);
        while (pq.size() != 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            Node parent = new Node(left, right, left.freq + right.freq, '\0');
            pq.add(parent);
            System.out.println(pq);
        }
        Huffman_Tree ht = new Huffman_Tree();
        String ans = "";
        ht.inOrder(pq.poll(), ans);
    }
}

class Node implements Comparable<Node> {

    @Override
    public String toString() {
        return "Node [freq=" + freq + ", ch=" + ch + "]";
    }

    Node lptr;
    Node rptr;
    int freq;
    char ch;

    Node(Node lptr, Node rptr, int freq, char ch) {
        this.freq = freq;
        this.lptr = lptr;
        this.rptr = rptr;
        this.ch = ch;
    }

    public int compareTo(Node o) {

        int comparedvalue = Integer.compare(this.freq, o.freq);
        if (comparedvalue != 0)
            return comparedvalue;
        else
            return Integer.compare(this.ch, o.ch);
        }
    }

    boolean isLeaf() {
        return this.lptr == null && this.rptr == null;
    }
}

class Huffman_Tree {
    void inOrder(Node root, String code) {
        if (!root.isLeaf()) {
            inOrder(root.lptr, code + '0');
            inOrder(root.rptr, code + '1');

        } else
            System.out.println(root.ch + " : " + code);

    }
}

Here, for input string abccddeeee, I'm getting something like:

[Node [freq=1, ch=a], Node [freq=1, ch=b], Node [freq=2, ch=c], Node [freq=2, ch=d], Node [freq=4, ch=e]]
[Node [freq=2, ch= ]]

I'm confused why in the second step Node having 'd' is coming ahead from 'e'. This is getting me errors in final encoding. Why compareTo method is failing I cant understand.

getHashString returns a Hash which has characters in key and their freq in value.

1
  • Can you provide the code of the HashString class, in order to reproduce your problem? Jan 14, 2020 at 16:04

1 Answer 1

1

I can't figure out why the order of the elements in PriorityQueue is not the expected one after polling elements ant adding new "synthetic" elements, but I think you can solve the problem switching to a TreeSet, as I have done with success with

TreeSet<Node> pq = new TreeSet<Node>((n1, n2) -> n1.compareTo(n2)); // explicit but unnecessary comparator

and changind each pq.poll() invocation into pq.pollFirst()...

I hope this workaround can help you!

EDIT

As you can read in official PriorityQueue documentation, * The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).*

This should explain why the toString() method invocation shows queue elements in an order different than the expected priority order...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.