Heap Sort

[sehudson]

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?

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

[Junky]

Create a class to hold your data. Iterate over the Map, get data, create object, add to List.

[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.

[Junky]

No, the heapSort method parameter is an array of Comparable. So you make your custom class implement that interface.

[sehudson]

can you explain that to me? I basically have a Heap class that has the heap methods and my table class that has:

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

    }

[Junky]

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?

[sehudson]

fixed that :)

[Junky]

You do realise that all those if statements for each letter is doing the exact same thing and can be deleted.

[sehudson]

/*
 * 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;
    }

    }