Results 1 to 9 of 9

Thread: Heap Sort

  1. #1
    sehudson's Avatar
    sehudson is offline Senior Member
    Join Date
    Mar 2010
    Posts
    383
    Rep Power
    8

    Default 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?

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

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,807
    Rep Power
    10

    Default

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

  3. #3
    sehudson's Avatar
    sehudson is offline Senior Member
    Join Date
    Mar 2010
    Posts
    383
    Rep Power
    8

    Default

    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.

  4. #4
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,807
    Rep Power
    10

    Default

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

  5. #5
    sehudson's Avatar
    sehudson is offline Senior Member
    Join Date
    Mar 2010
    Posts
    383
    Rep Power
    8

    Default

    can you explain that to me? I basically have a Heap class that has the heap methods and my table class that has:
    Java 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;
        }
    
        }

  6. #6
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,807
    Rep Power
    10

    Default

    Java 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?

  7. #7
    sehudson's Avatar
    sehudson is offline Senior Member
    Join Date
    Mar 2010
    Posts
    383
    Rep Power
    8

    Default

    fixed that :)

  8. #8
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,807
    Rep Power
    10

    Default

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

  9. #9
    sehudson's Avatar
    sehudson is offline Senior Member
    Join Date
    Mar 2010
    Posts
    383
    Rep Power
    8

    Default

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

Similar Threads

  1. no heap space... need more heap
    By anupam.kumar in forum Advanced Java
    Replies: 3
    Last Post: 02-08-2010, 05:42 PM
  2. Using Merge Sort to sort an ArrayList of Strings
    By coldfire in forum New To Java
    Replies: 3
    Last Post: 03-13-2009, 02:03 AM
  3. How to sort a list using Bubble sort algorithm
    By Java Tip in forum Algorithms
    Replies: 3
    Last Post: 04-29-2008, 08:04 PM
  4. Heap Sort in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-16-2008, 10:27 PM
  5. Heap Sort
    By kesav2005 in forum Advanced Java
    Replies: 1
    Last Post: 11-13-2007, 12:40 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •