prog1_Heap.tar

Heap.java0000644000175000017500000000203511647176714015056 0ustar  jpeak5-crunchyjpeak5-crunchyimport java.util.List;
import java.util.ArrayList;


public class Heap {
private List<Integer> h = new ArrayList<Integer>();
private int k;

public Heap(int k) {
this.k=k;
}

public void insert(int i) {
h.add(i);
int j = h.size()-1;
if(j==0) {
return;
}
while(j!=0&&(h.get(j)<h.get(((int) Math.floor(((double) j-1)/k))))) {
int l =((int) Math.floor(((double) j-1)/k));
int temp = h.get(j);
h.set(j, h.get(l));
h.set(l, temp);
j=l;
}
}

public int extractMin() {
assert h.size()!=0;
int min = h.get(0);
if(h.size()==1) {
h.remove(0);
}
else {
h.set(0, h.get(h.size()-1));
h.remove(h.size()-1);
int done =0;
int node=0;
while(done==0) {
int minchild=1;
done=1;
for(int j=1; j<=k; j++) {
if((node*k+j)>=h.size()) {
break;
}
if(h.get(node*k+j)<h.get(node*k+minchild)) {
minchild=j;
}
}
if((node*k+1)>=h.size()) {
break;
}
if(h.get(node*k+minchild)<h.get(node)) {
done=0;
int temp = h.get(node);
h.set(node, h.get(node*k+minchild));
h.set(node*k+minchild, temp);
}
node=node*k+minchild;
}
}
return min;
}

public void printH() {
System.out.println(h);
}


}
karyHeapInput.txt0000644000175000017500000000112611647176714016663 0ustar  jpeak5-crunchyjpeak5-crunchyIN 766
IN 678
IN 542
IN 24000
IN 2000
IN 4000
IN 3000
IN 1000
IN 18000
IN 14000
IN 8000
IN 17000
IN 7000
IN 23000
IN 16000
IN 26000
IN 6000
IN 39000
IN 13000
IN 22000
IN 27000
IN 29000
IN 12000
IN 200
IN 100
IN 150
IN 120
EX
IN 38000
IN 25000
IN 33000
IN 32000
IN 21000
IN 37000
IN 11000
IN 10000
IN 639
IN 935
IN 873
IN 700
IN 690
IN 943
IN 779
EX
IN 35000
IN 20000
IN 31000
IN 30000
IN 34000
IN 9000
IN 19000
IN 5000
IN 523
IN 400
IN 350
IN 944
IN 778
IN 767
IN 677
IN 546
IN 321
EX
IN 429
IN 352
IN 295
IN 991
IN 833
IN 747
IN 568
IN 428
IN 42
IN 689
IN 520
IN 567
EX
IN 15000
IN 28000
IN 36000
output.txt0000644000175000017500000000045611647211320015423 0ustar  jpeak5-crunchyjpeak5-crunchy2-ary heap:
100
120
150
42
running time: 23219 microseconds.
4-ary heap:
100
120
150
42
running time: 1402 microseconds.
6-ary heap:
100
120
150
42
running time: 1138 microseconds.
8-ary heap:
100
120
150
42
running time: 1104 microseconds.
10-ary heap:
100
120
150
42
running time: 5119 microseconds.
READMEFIRST.txt0000644000175000017500000000027511647176714015650 0ustar  jpeak5-crunchyjpeak5-crunchyWritten by Michael Taboada and Jason Peak.

To run, type java TestHeap <file> where <file> is an input file like karyHeapInput.txt
The heap is stored in Heap.java.

Output is in output.txt
TestHeap.java0000644000175000017500000000203411647176714015715 0ustar  jpeak5-crunchyjpeak5-crunchyimport java.io.FileReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;


public class TestHeap {
public static void main(String[] args) throws IOException {

			PrintWriter pw = new PrintWriter("output.txt");
for(int j=2; j<=10; j+=2) {

		long start = System.nanoTime(); // requires java 1.5
		
		
Heap he = new Heap(j);

		StringBuffer debug = new StringBuffer();
			FileReader input = new FileReader(args[0]);
			BufferedReader bf = new BufferedReader(input);
			StringBuffer sb = new StringBuffer();
			String line = null;

pw.println(j+"-ary heap:");

			// Read through file one line at time. Print line # and line
			while ((line = bf.readLine()) != null) {
				String cmd = line.substring(0, 2);
				int key;
				key=0;
if(line.length()>2) {
key = Integer.parseInt(line.substring(3));
}
if("IN".equals(cmd)) {
he.insert(key);
}
else if("EX".equals(cmd)) {
pw.println(""+he.extractMin());
pw.flush();
}
}
pw.println("running time: "+(System.nanoTime()-start)/1000+" microseconds.");
pw.flush();

}
}
}