Binary Heap

Priority Queue

#include<stdio.h>
int pq[100000],n;
int cmd;
int main(){
    while(true){
        scanf("%d",&cmd); // cmd = 0 : push / cmd = 1 : top / cmd = 2 : pop / cmd = 3 : end
        if(cmd == 0){ // push
            scanf("%d",&pq[n]);
            int pos = n;
            while(pos>0 && pq[pos] > pq[(pos-1)/2]){
                int t = pq[pos];
                pq[pos] = pq[(pos-1)/2];
                pq[(pos-1)/2] = t;
                pos = (pos-1)/2;
            }
            n++;
        }else if(cmd == 1){ // top
            if(n==0) printf("NO DATA\n");
            else printf("TOP : %d\n",pq[0]);
        }else if(cmd == 2){ // pop
            if(n==0) continue;
            pq[0] = pq[n-1];
            n--;
            int pos = 0,newpos;
            while(true){
                newpos = -1;
                if(2*pos+1 >= n) break;
                if(pq[pos] < pq[2*pos+1]) newpos = 2*pos+1;
                if(2*pos+2 < n && pq[pos] < pq[2*pos+2] && pq[2*pos+2] > pq[2*pos+1]) newpos = 2*pos+2;
                if(newpos == -1) break;
                int t = pq[pos];
                pq[pos] = pq[newpos];
                pq[newpos] = t;
                pos = newpos;
            }
            //printf("n = %d\n",n);
        }else break;
    }
}