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

Filed under:
|
|

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

Related posts about java

Related posts about algorithm