Results 1 to 9 of 9

Thread: Heap Sort

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

    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,779
    Rep Power
    7

    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
    356
    Rep Power
    5

    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,779
    Rep Power
    7

    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
    356
    Rep Power
    5

    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,779
    Rep Power
    7

    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
    356
    Rep Power
    5

    Default

    fixed that :)

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

    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
    356
    Rep Power
    5

    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, 04: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, 01: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, 11:40 AM

Posting Permissions

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