# Thread: Heap Sort

1. ## 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. Create a class to hold your data. Iterate over the Map, get data, create object, add to List.

3. 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. No, the heapSort method parameter is an array of Comparable. So you make your custom class implement that interface.

5. 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;
File file = null;
JFileChooser fileopen = new JFileChooser();
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.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. 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. fixed that :)

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

9. 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.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;
File file = null;
JFileChooser fileopen = new JFileChooser();
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.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;
}

}```

#### Posting Permissions

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