Saturday, May 18, 2013

priority queue c++ code

For in-depth understanding of Data Structure and Algorithm concepts refer :

1) INTRODUCTION TO ALGORITHMS by Coremen Introduction to Algorithms, 3rd Edition From flipkart.com
Introduction to Algorithms, 3rd Edition From amazon.com
Introduction to Algorithms from amazon.in

2) DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron - DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron from flipkart.com
Data Structures Using C and C++ (2nd Edition) from amazon.com
Data Structures Using C and C++ from amazon.in

#include<iostream.h>
#include<conio.h>
#include<process.h>
int n;
void maxheapinsert(int [],int key);
void heapincreasekey(int a[],int i,int key);
int heapextractmax(int a[]);
int prioritymaximum(int a[]);
void max_heapify(int a[20],int n1);
int heapsize;
int left(int i)
{
    return(2*i);
}
int right(int i)
{
    return((2*i)+1);
}
void max_heapify(int A[20],int i)
{
    int l,r,largest,s;
    l=left(i);
    r=right(i);

    if(l<=heapsize && A[l]>A[i])
        largest=l;
    else
        largest=i;

    if(r<=heapsize && A[r]>A[largest])
        largest=r;

    if(largest!=i)
    {
        s=A[i];
        A[i]=A[largest];
        A[largest]=s;
        max_heapify(A,largest);
    }
}
int prioritymaximum(int a[])
{

    return a[1];
}
int heapextractmax(int a[])
{
    if(n<0)
        cout<<"Underflow"<<endl;
    int max=a[1];
    a[1]=a[n];
    n--;
    max_heapify(a,1);
    return max;
}

void heapincreasekey(int a[],int i,int k)
{
    if(k<a[i])
        cout<<"New key is smaller than current key"<<endl;
    a[i]=k;
    while(i>1&&a[i/2]<a[i])
    {
        int t=a[i];
        a[i]=a[i/2];
        a[i/2]=t;
        i=i/2;
    }
}
void maxheapinsert(int a[],int k)
{
    n=n+1;
    a[n]=-999;
    heapincreasekey(a,n,k);
}

void main()
{
    int x,i2,c,key,a[20];
    a[0]=-999;
    int m;
    for(  ;  ; )
    {
        cout<<"Menu:"<<endl;
        cout<<"1:To get the maximum value"<<endl;
        cout<<"2:To extract maximum value"<<endl;
        cout<<"3:To increase key value"<<endl;
        cout<<"4:To insert new value"<<endl;
        cout<<"5:Exit:"<<endl;
        cout<<"Enter your choice"<<endl;
        cin>>c;
        switch(c)
        {
            case 1:
                x=prioritymaximum(a);
                cout<<x<<endl;
                break;
            case 2:
                m=heapextractmax(a);cout<<"process with priority "<<m<<" is being processed";
                break;
            case 3:
                cout<<"Enter the index value that is to modified "<<endl;
                cin>>i2;
                cout<<"Enter the new value"<<endl;
                cin>>key;
                heapincreasekey(a,i2,key);
                cout<<"Value modified"<<endl;
                break;
            case 4:
                cout<<"Enter the new value"<<endl;
                cin>>key;
                maxheapinsert(a,key);
                break;
            case 5:
                exit(0);
            default:
                cout<<"Wrong code"<<endl;
        }
    }
    getch();
}

No comments:

Post a Comment