priority queue implementation
Posted
by davit-datuashvili
on Stack Overflow
See other posts from Stack Overflow
or by davit-datuashvili
Published on 2010-05-25T07:32:01Z
Indexed on
2010/05/25
7:51 UTC
Read the original article
Hit count: 133
i have implemented priority queue and i am interested if it is correct
public class priqueue {
private int n,maxsize;
int x[];
void swap(int i,int j){
int t=x[i];
x[i]=x[j];
x[j]=t;
}
public priqueue(int m){
maxsize=m;
x=new int [maxsize+1];
n=0;
}
void insert(int t){
int i,p;
x[++n]=t;
for (i=n;i>1 && x[p=i/2] >x[i];i=p)
swap(p,i);
}
public int extramin(){
int i,c;
int t=x[1];
x[1]=x[n--];
for (i=1;(c=2*i)<=n;i=c){
if (c+1<=n && x[c+1]<x[c])
c++;
if (x[i]<=x[c])
break;
swap(c,i);
}
return t;
}
public void display(){
for (int j=0;j<x.length;j++){
System.out.println(x[j]);
}
}
}
public class priorityqueue {
public static void main(String[] args) {
priqueue pr=new priqueue(12);
pr.insert(20);
pr.insert(12);
pr.insert(22);
pr.insert(15);
pr.insert(35);
pr.insert(17);
pr.insert(40);
pr.insert(51);
pr.insert(26);
pr.insert(19);
pr.insert(29);
pr.insert(23);
pr.extramin();
pr.display();
}
}
//result: 0 12 15 17 20 19 22 40 51 26 35 29 23
© Stack Overflow or respective owner