Advertisement

04.24.2008 at 04:42PM PDT, ID: 23352293
[x]
Attachment Details

Huffman Code: minHeapify and insert, Java

Asked by Brad87 in Algorithms

Tags: Java, Binary Heap, minHeapify, Heap insert

I am writing code to read in a text file and to encode it with huffman code using a min heap and priority queue. I have the file read in and stored in a Table and I can insert the Content of the table into TreeNodes in a BST but i need it to be a minHeap. how can can i insert the nodes so it is a minHeap when the insertion is complete and I also need a little help with the minHeapify method.
Right now my nodes have a left right and parent fields for pointers, do i need some other kind of pointer? I was reading somewhere that I need a successor pointer. If so how would I go about it and why do i need it?Start Free Trial 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:

TreeNode root = new TreeNode();
TreeNode node2 = null;
BinaryTree tree1=new BinaryTree();
int size=1;
   // insert: insert new node into the tree
   //public void insert(TreeNode t) {
public TreeNode insert(TreeNode node, char newChar, int newFreq) {
       if (node==null) { 
           size++;
      node = new TreeNode(newChar, newFreq); 
    } 
    else { 
      if (newFreq <= node.frequency) { 
          //node.leftChild.Parent=node;
        //node.leftChild = insert(node.leftChild, newChar, newFreq);
          node.leftChild = insert2(node.leftChild, node, newChar, newFreq);
      } 
      else { 
         // node.rightChild.Parent=node;
        //node.rightChild = insert(node.rightChild,newChar, newFreq); 
          node.rightChild = insert2(node.rightChild,node,newChar, newFreq); 
      } 
    } 
 
    return(node); // in any case, return the new pointer to the caller 
 
   }
public TreeNode insert2(TreeNode node, TreeNode previousNode, char newChar, int newFreq) {
    
       if (node==null) { 
           size++;
      node = new TreeNode(newChar, newFreq); 
      node.Parent=previousNode;
    } 
    else { 
      if (newFreq <= node.frequency) {
          //node.Parent=previousNode;
          
        node.leftChild = insert2(node.leftChild,node, newChar, newFreq); 
      } 
      else { 
         // node.Parent=previousNode;
        node.rightChild = insert2(node.rightChild,node, newChar, newFreq); 
      } 
    } 
 
    return(node); // in any case, return the new pointer to the caller 
}
 
 
 
static TreeNode MinHeapify(TreeNode node)
     {
         TreeNode l= node.leftChild;
         TreeNode r= node.rightChild;
         TreeNode smallest;
         if(node.Parent!=null){
         if(l.frequency<node.frequency){
             System.out.println("l.frequency<node.frequency executed");
             smallest=l;
         }
             
         else
             smallest=node;
         if(r.frequency<smallest.frequency){
             System.out.println("r.frequency<smallest.frequency executed");
             smallest=r;
         }
             
         if (smallest!=node);
         {
             System.out.println("if (smallest!=node) executed");
             exchange(node,smallest);
             MinHeapify(node);
         }
         }
         else
             System.out.println("Parent is null");
         return node;
         //else 
          //  throw new TreeException("TreeException: MinHeapify Pointing at root");
     }
     
     static TreeNode exchange(TreeNode node, TreeNode node2)
     {
         TreeNode first=node;
         TreeNode second=node2;
         node2=first;
         node=second;
             return node;
     }
 
   // buildList: create the initial list with singleton trees
   public void buildTree(Entry[] tab, int n) {
      try{
       int i;
      TreeNode tNode;
      TreeNode sNode;
      
      sNode = new TreeNode();
      sNode.leftChild = sNode.rightChild = null;
        
            
          FileOutputStream fout = new FileOutputStream("table.txt");
           PrintStream myOutput = new PrintStream(fout);
            
             myOutput.println("Letter        Frequency");
             sNode.setCharacter(tab[0].symb);
             sNode.setFrequency(tab[0].freq);
             root=sNode;
             //sNode.leftChild = tNode;
      for (i = 1; i < n; i++) {
         tNode = new TreeNode();
        // tNode.weight = tab[i].weight;
         tNode.leftChild = tNode.rightChild = null;
         tNode.setCharacter(tab[i].symb) ;
         tNode.setFrequency(tab[i].freq);
        
         //System.out.print(tNode.getCharacter());
        // System.out.println(tNode.getFrequency());
       
          
         myOutput.print(tNode.getCharacter()+"            ");
         myOutput.println(tNode.getFrequency());  
         //Output.Output1(tNode.getCharacter(),tNode.getFrequency());
        // tNode.rep = "";
         //BinaryTree2.insert(tNode,tNode.frequency,tNode.character);
         insert(root,tNode.character,tNode.frequency);
      }
             
             //TreeNode.preorderPrint( sNode );
             //TreeNode.preorderPrint( sNode );
            //sNode= MinHeapify(sNode);
            //TreeNode.preorderPrint( sNode );
            // System.out.println(sNode.frequency);
            //System.out.println(sNode.leftChild.frequency);
           // System.out.println(sNode.rightChild.frequency);
           // System.out.println(sNode.rightChild.leftChild.frequency);
            //System.out.println(sNode.rightChild.rightChild.frequency);
            System.out.println(size);
            }
      
         catch (IOException e)
          {
            System.err.println ("Unable to read from file");
            System.exit(-1);
          }
   }
[+][-]04.25.2008 at 11:06AM PDT, ID: 21441916

View this solution now by starting your 7-day free trial. Setting up your free trial is quick, easy, and secure. We will return you to this solution, unlocked, when you're done.

 

About this solution

Zone: Algorithms
Tags: Java, Binary Heap, minHeapify, Heap insert
Sign Up Now!
Solution Provided By: roussosc
Participating Experts: 2
Solution Grade: A
 
 
 
Loading Advertisement...
20080716-EE-VQP-32 / EE_QW_2_20070628