i wrote a code to implement some basics of priority queue , but apparantly its not giving desired output. the code is implemented using binary heap as its data structure. i tried tinkering here and there , nut no luck... i want to display a given number of max or min items, but im just getting a random selection of words from the file as output. any help with the code will be great. :)
this is my priority queue code:
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
private int N;
// create an empty priroty queue
@SuppressWarnings("unchecked")
public MaxPQ(int capacity){
pq = (Key[])new Comparable[capacity+1];
}
//insert a key into a priority queue
public void insert(Key v){
pq[++N] = v;
swim(N);
}
public int size(){
return N;
}
// delete the max key
public Key delMax(){
Key max = pq[1];
exch(1,N--);
sink(1);
pq[N+1] = null;
return max;
}
public Key delMin(){
Key min = pq[N--];
pq[N+1] = null;
return min;
}
// is the priority queue empty
public boolean isEmpty(){
return N == 0;
}
private void swim(int k){
while(k>1 && less(k/2,k)){
exch(k,k/2);
k = k/2;
}
}
private void sink(int k){
while(2*k <= N){
int j = 2*k;
if( j < N && less(j,j+1)) j++;
if(!less(k,j)) break;
exch(k,j);
k=j;
}
}
private boolean less(int i,int j){
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i , int j){
Key temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
public void displayItems(){
for(Key i : pq)
System.out.println(" " + i);
}
}
this is the tester method
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileNotFoundException;
import java.io.IOException;
public class testerPQ {
public static void main(String[] args) throws FileNotFoundException{
MaxPQ<String> pq = new MaxPQ<String>(3);
BufferedReader is = new BufferedReader(new FileReader("C:/Documents and Settings/Somjit/Desktop/pqtest.txt"));
String Line;
try {
while((Line = is.readLine()) != null){
pq.insert(Line);
if(pq.size() > 2)
pq.delMin();
}
} catch (IOException e) {
e.printStackTrace();
}
pq.displayItems();
System.out.println("finished executing");
}
}
and this is the file from which the code is reading :
a
hi
cat
lion
tiger
monkey
dinosaur
hippopotamus
jurrasicparkthree
kjhkjhkjhkjhkjhkjhh