# Heap Sort

• 03-31-2011, 02:28 AM
sehudson
Heap Sort
I am trying to get 'nodes' into a minHeap, such that the node contains a character and its frequency (A:9) for example. I have the key/value pairs in a hashmap. Is there a way to create a 'node' of some sort out of the key/value, so that I can put them into an array, and pass it to my 'heapsort' method?

Code:

```    public Heap(){     }     public static void heapsort( Comparable [ ] a )     {         for( int i = a.length / 2; i >= 0; i-- )  /* buildHeap */             percDown( a, i, a.length );         for( int i = a.length - 1; i > 0; i-- )         {             swapReferences( a, 0, i );            /* deleteMax */             percDown( a, 0, i );         }     }     /**     * Internal method for heapsort.     * @param i the index of an item in the heap.     * @return the index of the left child.     */     private static int leftChild( int i )     {         return 2 * i + 1;     }     /**     * Internal method for heapsort that is used in     * deleteMax and buildHeap.     * @param a an array of Comparable items.     * @index i the position from which to percolate down.     * @int n the logical size of the binary heap.     */     private static void percDown( Comparable [ ] a, int i, int n )     {         int child;         Comparable tmp;         for( tmp = a[ i ]; leftChild( i ) < n; i = child )         {             child = leftChild( i );             if( child != n - 1 && a[ child ].compareTo( a[ child + 1 ] ) < 0 )                 child++;             if( tmp.compareTo( a[ child ] ) < 0 )                 a[ i ] = a[ child ];             else                 break;         }         a[ i ] = tmp;     }     /**     * Method to swap to elements in an array.     * @param a an array of objects.     * @param index1 the index of the first object.     * @param index2 the index of the second object.     */     public static final void swapReferences( Object [ ] a, int index1, int index2 )     {         Object tmp = a[ index1 ];         a[ index1 ] = a[ index2 ];         a[ index2 ] = tmp;     } }```
• 03-31-2011, 02:56 AM
Junky
Create a class to hold your data. Iterate over the Map, get data, create object, add to List.
• 03-31-2011, 03:12 AM
sehudson
problem is, the heapSort method wants an array with ONLY the values ( i believe), so it can create the heap(array) of integers.
Then, I have to somehow create an arrayList that has the int values AND the letter they pair with, so that I can print them out.

So for example if I have a string 'This is only a test', my hashmap that I'm creating looks like(no difference between upper and lower):

t-3
h-1
i-2
s-3
space -4
o-1
n-1
l-1
y-1
a-1
e-1

So when I Iterate over the map values and insert those values into an array, I pass that array to my heapSort method, and that yields an array with:
1
1
1
1
1
1
1
2
3
3
4

Now, I have to figure out how to print out 'a:1 t:3' etc.
• 03-31-2011, 03:14 AM
Junky
No, the heapSort method parameter is an array of Comparable. So you make your custom class implement that interface.
• 03-31-2011, 03:19 AM
sehudson
can you explain that to me? I basically have a Heap class that has the heap methods and my table class that has:
Code:

```public class Table extends HashMap<Character,Integer> {     public HashMap map;     int occurences;     public Comparable[] heapValsToArray;     public Table(){     map = new HashMap<Character,Integer>();     }     public void createTable() {         int count = 0;         InputStreamReader isr;         File file = null;         JFileChooser fileopen = new JFileChooser();         fileopen.setDialogTitle("Please choose your file");         int ret = fileopen.showDialog(null, "Open file");         if (ret == JFileChooser.APPROVE_OPTION) {             file = fileopen.getSelectedFile();         }         try {             isr = new InputStreamReader(new FileInputStream(file));             int c;             //Add key-value pairs to the hash map for each character found.             while ((c = isr.read()) !=-1) {                 char ch = (char) c;                 System.out.println("Found "+ch);                 UpdateFrequency(map,ch);             }             isr.close();         } catch (FileNotFoundException E) {             System.out.println("File not found: ");             System.exit(1);         } catch (java.io.IOException ioe) {             System.out.println("IO Problem");             System.exit(1);         }         //Add the hash map values to an array, so that we can create/sort a heap.         Iterator iterator = map.values().iterator();         heapValsToArray = new Comparable[map.size()];         while(iterator.hasNext()){         int current = (Integer)iterator.next();         heapValsToArray[count] = current;         count++;         }         Heap.heapsort(heapValsToArray);     }     public void UpdateFrequency(HashMap table,char ch){     if (ch=='A' || ch=='a'){         if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='B' || ch=='b'){         if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='C' || ch=='c'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='D' || ch=='d'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='E' || ch=='e'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='F' || ch=='f'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='G' || ch=='g'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='H' || ch=='h'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='I' || ch=='i'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='J' || ch=='j'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='K' || ch=='k'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='L' || ch=='l'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='M' || ch=='m'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='N' || ch=='n'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='O' || ch=='o'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='P' || ch=='p'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='Q' || ch=='q'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='R' || ch=='r'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='S' || ch=='s'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='T' || ch=='t'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='U' || ch=='u'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='V' || ch=='v'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='W' || ch=='w'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='X' || ch=='x'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='Y' || ch=='y'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='Z' || ch=='z'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }         if (ch==' '){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     }     public int getFrequency(HashMap table,char Character){         int instances = 0;         if(table.get(Character)==null){           instances = 0;         }         else{         instances = (Integer)table.get(Character);         }         return instances;     }     }```
• 03-31-2011, 03:22 AM
Junky
Code:

```public class Table extends HashMap<Character,Integer> {     public HashMap map;```
If your class extends HashMap why do you create an instance of a HashMap inside the class?
• 03-31-2011, 03:24 AM
sehudson
fixed that :)
• 03-31-2011, 03:25 AM
Junky
You do realise that all those if statements for each letter is doing the exact same thing and can be deleted.
• 03-31-2011, 03:25 AM
sehudson
Code:

```/*  * To change this template, choose Tools | Templates  * and open the template in the editor.  */ package huffmanalgorithm; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Iterator; import javax.swing.JFileChooser; /**  *  * @author Steve  */ public class Table extends HashMap<Character,Integer> {     int occurences;     public Comparable[] heapValsToArray;     public Table(){     }     public void createTable() {         int count = 0;         InputStreamReader isr;         File file = null;         JFileChooser fileopen = new JFileChooser();         fileopen.setDialogTitle("Please choose your file");         int ret = fileopen.showDialog(null, "Open file");         if (ret == JFileChooser.APPROVE_OPTION) {             file = fileopen.getSelectedFile();         }         try {             isr = new InputStreamReader(new FileInputStream(file));             int c;             //Add key-value pairs to the hash map for each character found.             while ((c = isr.read()) !=-1) {                 char ch = (char) c;                 System.out.println("Found "+ch);                 UpdateFrequency(this,ch);             }             isr.close();         } catch (FileNotFoundException E) {             System.out.println("File not found: ");             System.exit(1);         } catch (java.io.IOException ioe) {             System.out.println("IO Problem");             System.exit(1);         }         //Add the hash map values to an array, so that we can create/sort a heap.         Iterator iterator = this.values().iterator();         heapValsToArray = new Comparable[this.size()];         while(iterator.hasNext()){         int current = (Integer)iterator.next();         heapValsToArray[count] = current;         count++;         }         Heap.heapsort(heapValsToArray);         for(int i=0; i<heapValsToArray.length; i++){         }     }     public void UpdateFrequency(HashMap table,char ch){     if (ch=='A' || ch=='a'){         if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='B' || ch=='b'){         if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='C' || ch=='c'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='D' || ch=='d'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='E' || ch=='e'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='F' || ch=='f'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='G' || ch=='g'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='H' || ch=='h'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='I' || ch=='i'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='J' || ch=='j'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='K' || ch=='k'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='L' || ch=='l'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='M' || ch=='m'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='N' || ch=='n'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='O' || ch=='o'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='P' || ch=='p'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='Q' || ch=='q'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='R' || ch=='r'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='S' || ch=='s'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='T' || ch=='t'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='U' || ch=='u'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='V' || ch=='v'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='W' || ch=='w'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='X' || ch=='x'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='Y' || ch=='y'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     if (ch=='Z' || ch=='z'){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }         if (ch==' '){                 if(table.get(ch)==null){         occurences=1;         table.put(ch, occurences);         }         else{         int howMany = (Integer)table.get(ch);         occurences = howMany+1;         table.put(ch, occurences);         }     }     }     public int getFrequency(HashMap table,char Character){         int instances = 0;         if(table.get(Character)==null){           instances = 0;         }         else{         instances = (Integer)table.get(Character);         }         return instances;     }     }```