RSS

Priority Queue

C++ code for implementing Priority Queue:

 

#include<iostream.h>
#include<conio.h>
int i=0,n=0,l,r,heapsize,smallest,temp,j,B[100],C[100],k;

int parent(int i)
{int x;
if(i%2==0)
x=i%2;
else
x=(i-1)/2;
return x;
}

void minpriority(int A[],int i)
{

l=2*i;//left of i
r=1+l;//right of i
if(l<=heapsize && A[l]<A[i])
smallest=l;
else
smallest=i;
if(r<=heapsize && A[r]<A[smallest])
smallest=r;
if(smallest!=i)
{
temp=A[i];
A[i]=A[smallest];
A[smallest]=temp;
minpriority(A,smallest);
}
}


void buildminpriority(int A[])
{
heapsize=n-1;
for(i=n-1;i>=0;i–)
minpriority(A,i);
}

void decreasekey(int A[],int i,int key)
{
if(key>A[i])
cout<<“New key is greater than current key, hence no decreasing.”<<endl;
else
{A[i]=key;
while(i>=0 && A[parent(i)]>A[i])
{temp=A[i];
A[i]=A[parent(i)];
A[parent(i)]=temp;
i=parent(i);}
}
}


void insert(int A[],int key)
{

A[heapsize]=10000;
decreasekey(A,heapsize,key);
}


void extractmin(int A[],int i)
{int min;
if(heapsize<0)
cout<<“Heap Underflow”<<endl;
else
{min=A[0];
A[0]=A[heapsize];
heapsize=heapsize-1;
minpriority(A,0);
cout<<“Value of Minimum is:”<<min<<endl;
}}









void main()
{

cout<<“Enter the size of the array”<<endl;
cin>>n;

cout<<“Enter the values”<<endl;
for(j=0;j<n;j++)
{cin>>B[j];
}

cout<<“Enter the key”<<endl;
cin>>k;
cout<<“Values of priority queue initially:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;


buildminpriority(B);
cout<<“Values of priority queue after building:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;



extractmin(B,i);
cout<<“Values of priority queue after extracting:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;




decreasekey(C,i,k);
cout<<“Values of priority queue after decreasing key:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;




insert(B,k);
cout<<“Values of priority queue after inserting:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;
}//end main

 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

Building Max Heap

Code for Max Heap… Shows the use of MaxHeapify:

#include<iostream.h>
#include<math.h>
int size;
void maxheapify(int a[],int i,int size)
{
int l,r,largest,temp;
l=2*i;
r=(2*i+1);
if((l<=size) && (a[l]>a[i]))
largest=l;
else
largest=i;
if((r<=size) && (a[r]>a[largest]))
largest=r;
if(largest!=i)
{
temp=a[i];
a[i]=a[largest];
a[largest]=temp;
maxheapify(a,largest,size);
}
};
void buildmaxheap(int a[],int size)
{
int i;
for(i=floor(size/2);i>=1;i–)
{
maxheapify(a,i,size);
}
}
int extract_max(int*a,int size)
{
int max;
max=a[1];
a[1]=a[size];
size–;
maxheapify(a,1,size);
return(max);
}
void main()
{
int p,k,i,max,a[20],temp;
cout<<“How many no u want 2 enter\n”;
cin>>size;
cout<<“Enter no\n”;
for(i=1;i<=size;i++)
{
cin>>a[i];
}
buildmaxheap(a,size);
cout<<“Enter the value of k\n”;
cin>>k;
if(k>size)
cout<<“The value entered is greater than heap size\n”;
else
{
for(i=0;i<k;i++)
{
max=extract_max(a,size);
}
cout<<“The kth largest element is:-    “<<max;
}
}
 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

Merge Sort

C Program for implementing merge-sort

#include<conio.h>
#include<stdio.h>
#define MAX 5

int a[MAX],i;
void meage_sort(int a[],int,int);
void split(int a[],int,int,int,int);
void main()
{
clrscr();
for (int i=0;i<MAX;i++)
{
printf(“\n enter %d element “,i+1);
scanf(“%d”,&a[i]);
}
meage_sort(a,0,MAX-1);
printf(“\n UR DATA AFTER SORTING\n “);
for(i=0;i<MAX;i++)
{
printf(“%d->”,a[i]);
}
getch();
}

void meage_sort(int a[],int lower, int upper)
{
int mid;

if(lower<upper)
{
mid=(lower+upper)/2;
meage_sort(a,lower,mid);
meage_sort(a,mid+1,upper);
split(a,lower,mid,mid+1,upper);
}
}
void split(int a[],int low1,int up1,int low2,int up2)
{
int p,q,j,n;
int temp[MAX];
p=low1;
q=low2;
n=0;
while((p<=up1) && (q<=up2))
temp[n++]=(a[p] < a[q] ? a[p++]:a[q++]);
while(p<=up1)
temp[n++]=a[p++];
while(q<=up2)
temp[n++]=a[q++];

for(q=low1,n=0 ;q<=up1 ;q++,n++)
a[q]=temp[n];
for(q=low2,j=n ;q<=up2 ;q++,j++)
a[q]=temp[j];
}

 

 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

Insertion/Deletion in B tree

Program of insertion and deletion in B tree

 

#include
#include
#define M 5

struct node{
int n; /* n < M No. of keys in node will always less than order of B
tree */
int keys[M-1]; /*array of keys*/
struct node *p[M]; /* (n+1 pointers will be in use) */
}*root=NULL;

enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys };

void insert(int key);
void display(struct node *root,int);
void DelNode(int x);
void search(int x);
enum KeyStatus ins(struct node *r, int x, int* y, struct node** u);
int searchPos(int x,int *key_arr, int n);
enum KeyStatus del(struct node *r, int x);

int main()
{
int key;
int choice;
printf(“Creation of B tree for node %d\n”,M);
while(1)
{
printf(“1.Insert\n”);
printf(“2.Delete\n”);
printf(“3.Search\n”);
printf(“4.Display\n”);
printf(“5.Quit\n”);
printf(“Enter your choice : “);
scanf(“%d”,&choice);

switch(choice)
{
case 1:
printf(“Enter the key : “);
scanf(“%d”,&key);
insert(key);
break;
case 2:
printf(“Enter the key : “);
scanf(“%d”,&key);
DelNode(key);
break;
case 3:
printf(“Enter the key : “);
scanf(“%d”,&key);
search(key);
break;
case 4:
printf(“Btree is :\n”);
display(root,0);
break;
case 5:
exit(1);
default:
printf(“Wrong choice\n”);
break;
}/*End of switch*/
}/*End of while*/
return 0;
}/*End of main()*/

void insert(int key)
{
struct node *newnode;
int upKey;
enum KeyStatus value;
value = ins(root, key, &upKey, &newnode);
if (value == Duplicate)
printf(“Key already available\n”);
if (value == InsertIt)
{
struct node *uproot = root;
root=malloc(sizeof(struct node));
root->n = 1;
root->keys[0] = upKey;
root->p[0] = uproot;
root->p[1] = newnode;
}/*End of if */
}/*End of insert()*/

enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node
**newnode)
{
struct node *newPtr, *lastPtr;
int pos, i, n,splitPos;
int newKey, lastKey;
enum KeyStatus value;
if (ptr == NULL)
{
*newnode = NULL;
*upKey = key;
return InsertIt;
}
n = ptr->n;
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
return Duplicate;
value = ins(ptr->p[pos], key, &newKey, &newPtr);
if (value != InsertIt)
return value;
/*If keys in node is less than M-1 where M is order of B tree*/
if (n < M – 1)
{
pos = searchPos(newKey, ptr->keys, n);
/*Shifting the key and pointer right for inserting the new key*/
for (i=n; i>pos; i–)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
/*Key is inserted at exact location*/
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
++ptr->n; /*incrementing the number of keys in node*/
return Success;
}/*End of if */
/*If keys in nodes are maximum and position of node to be inserted is
last*/
if (pos == M – 1)
{
lastKey = newKey;
lastPtr = newPtr;
}
else /*If keys in node are maximum and position of node to be inserted
is not last*/
{
lastKey = ptr->keys[M-2];
lastPtr = ptr->p[M-1];
for (i=M-2; i>pos; i–)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
}
splitPos = (M – 1)/2;
(*upKey) = ptr->keys[splitPos];

(*newnode)=malloc(sizeof(struct node));/*Right node after split*/
ptr->n = splitPos; /*No. of keys for left splitted node*/
(*newnode)->n = M-1-splitPos;/*No. of keys for right splitted node*/
for (i=0; i < (*newnode)->n; i++)
{
(*newnode)->p[i] = ptr->p[i + splitPos + 1];
if(i < (*newnode)->n – 1)
(*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
else
(*newnode)->keys[i] = lastKey;
}
(*newnode)->p[(*newnode)->n] = lastPtr;
return InsertIt;
}/*End of ins()*/

void display(struct node *ptr, int blanks)
{
if (ptr)
{
int i;
for(i=1;i<=blanks;i++)
printf(” “);
for (i=0; i < ptr->n; i++)
printf(“%d “,ptr->keys[i]);
printf(“\n”);
for (i=0; i <= ptr->n; i++)
display(ptr->p[i], blanks+10);
}/*End of if*/
}/*End of display()*/

void search(int key)
{
int pos, i, n;
struct node *ptr = root;
printf(“Search path:\n”);
while (ptr)
{
n = ptr->n;
for (i=0; i < ptr->n; i++)
printf(” %d”,ptr->keys[i]);
printf(“\n”);
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
{
printf(“Key %d found in position %d of last dispalyed
node\n”,key,i);
return;
}
ptr = ptr->p[pos];
}
printf(“Key %d is not available\n”,key);
}/*End of search()*/

int searchPos(int key, int *key_arr, int n)
{
int pos=0;
while (pos < n && key > key_arr[pos])
pos++;
return pos;
}/*End of searchPos()*/

void DelNode(int key)
{
struct node *uproot;
enum KeyStatus value;
value = del(root,key);
switch (value)
{
case SearchFailure:
printf(“Key %d is not available\n”,key);
break;
case LessKeys:
uproot = root;
root = root->p[0];
free(uproot);
break;
}/*End of switch*/
}/*End of delnode()*/

enum KeyStatus del(struct node *ptr, int key)
{
int pos, i, pivot, n ,min;
int *key_arr;
enum KeyStatus value;
struct node **p,*lptr,*rptr;

if (ptr == NULL)
return SearchFailure;
/*Assigns values of node*/
n=ptr->n;
key_arr = ptr->keys;
p = ptr->p;
min = (M – 1)/2;/*Minimum number of keys*/

pos = searchPos(key, key_arr, n);
if (p[0] == NULL)
{
if (pos == n || key < key_arr[pos])
return SearchFailure;
/*Shift keys and pointers left*/
for (i=pos+1; i < n; i++)
{
key_arr[i-1] = key_arr[i];
p[i] = p[i+1];
}
return –ptr->n >= (ptr==root ? 1 : min) ? Success : LessKeys;
}/*End of if */

if (pos < n && key == key_arr[pos])
{
struct node *qp = p[pos], *qp1;
int nkey;
while(1)
{
nkey = qp->n;
qp1 = qp->p[nkey];
if (qp1 == NULL)
break;
qp = qp1;
}/*End of while*/
key_arr[pos] = qp->keys[nkey-1];
qp->keys[nkey – 1] = key;
}/*End of if */
value = del(p[pos], key);
if (value != LessKeys)
return value;

if (pos > 0 && p[pos-1]->n > min)
{
pivot = pos – 1; /*pivot for left and right node*/
lptr = p[pivot];
rptr = p[pos];
/*Assigns values for right node*/
rptr->p[rptr->n + 1] = rptr->p[rptr->n];
for (i=rptr->n; i>0; i–)
{
rptr->keys[i] = rptr->keys[i-1];
rptr->p[i] = rptr->p[i-1];
}
rptr->n++;
rptr->keys[0] = key_arr[pivot];
rptr->p[0] = lptr->p[lptr->n];
key_arr[pivot] = lptr->keys[–lptr->n];
return Success;
}/*End of if */
if (posn > min)
{
pivot = pos; /*pivot for left and right node*/
lptr = p[pivot];
rptr = p[pivot+1];
/*Assigns values for left node*/
lptr->keys[lptr->n] = key_arr[pivot];
lptr->p[lptr->n + 1] = rptr->p[0];
key_arr[pivot] = rptr->keys[0];
lptr->n++;
rptr->n–;
for (i=0; i < rptr->n; i++)
{
rptr->keys[i] = rptr->keys[i+1];
rptr->p[i] = rptr->p[i+1];
}/*End of for*/
rptr->p[rptr->n] = rptr->p[rptr->n + 1];
return Success;
}/*End of if */

if(pos == n)
pivot = pos-1;
else
pivot = pos;

lptr = p[pivot];
rptr = p[pivot+1];
/*merge right node with left node*/
lptr->keys[lptr->n] = key_arr[pivot];
lptr->p[lptr->n + 1] = rptr->p[0];
for (i=0; i < rptr->n; i++)
{
lptr->keys[lptr->n + 1 + i] = rptr->keys[i];
lptr->p[lptr->n + 2 + i] = rptr->p[i+1];
}
lptr->n = lptr->n + rptr->n +1;
free(rptr); /*Remove right node*/
for (i=pos+1; i < n; i++)
{
key_arr[i-1] = key_arr[i];
p[i] = p[i+1];
}
return –ptr->n >= (ptr == root ? 1 : min) ? Success : LessKeys;
}/*End of del()*/

 

 

 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

Min Heap

Min Heap C program

#include<iostream.h>
#include<conio.h>
int heapsize;
void minheap(int*,int);
void insert(int*,int);
int extract_min(int*);
void decrease_key(int*,int,int);
void decreasekey(int*,int,int);
void main()
{
int i,start,A[10],min,position,key;
cout<<“Enter the number to be inserted\n”;
cin>>heapsize;
cout<<” enter the numbers\n”;
for(i=1;i<=heapsize;i++)
{
cin>>A[i];
}
start=heapsize/2;
while(start>0)
{
minheap(A,start);
start–;
}
cout<<“\nThe  minheap is:-\n”;
for(i=1;i<=heapsize;i++)
{
cout<<A[i]<<“\n”;
}

cout<<“\nThe extract min operation:-\n”;
min=extract_min(A);
cout<<“The minimum value of heap is : “<<min<<“\n\n”;
cout<<“The resulting minheap is:-\n”;
for(i=1;i<=heapsize;i++)
{
cout<<A[i]<<“\n”;
}

cout<<“\nThe decrease key operation:-\n”;
cout<<“Enter any key with its position\n”;
cin>>key>>position;
decrease_key(A,position,key);
cout<<“\nThe resulting minheap is:-\n”;
for(i=1;i<=heapsize;i++)
{
cout<<A[i]<<“\n”;
}

cout<<“\nThe insert key operation:-\n”;
cout<<“Enter the key u want 2 insert\n”;
cin>>key;
insert(A,key);
cout<<“\nThe resulting minheap is:-\n”;
for(i=1;i<=heapsize;i++)
{
cout<<A[i]<<“\n”;
}
}

void minheap(int*A,int i)
{
int lc,rc,minimum,num;
lc=(2*i);
rc=lc+1;
if((lc<=heapsize)&&(A[lc]<A[i]))
minimum=lc;
else
minimum=i;
if((rc<=heapsize)&&(A[rc]<A[minimum]))
minimum=rc;
if(minimum!=i)
{
num=A[i];
A[i]=A[minimum];
A[minimum]=num;
minheap(A,minimum);
}}

int extract_min(int*A)
{
int min;
min=A[1];
A[1]=A[heapsize];
heapsize–;
minheap(A,1);
return(min);
}

void decrease_key(int*A,int i,int key)
{
int parent,num;
parent=i/2;
if(A[i]<key)
cout<<“Cannot increase key as already smaller\n”;
else
A[i]=key;
while((i>1)&&(A[parent]>A[i]))
{
num=A[i];
A[i]=A[parent];
A[parent]=num;
i=parent;
parent=i/2;
}
}

void decreasekey(int*A,int i,int key)
{
int parent,num;
parent=i/2;
A[i]=key;
while((i>1)&&(A[parent]>A[i]))
{
num=A[i];
A[i]=A[parent];
A[parent]=num;
i=parent;
parent=i/2;
}
}

void insert(int*A,int key)
{
heapsize++;
A[heapsize]=-1000;
decreasekey(A,heapsize,key);
}
 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

Insertion/Deletion in a Queue Data Structure

Insertion/Deletion in a Queue Data Structure in C

#include<stdio.h>
#include<conio.h>
#include<process.h>
int queue[5];
long front,rear;
void display();
void main()
{
int choice,info;
clrscr();
//initilisin queue
int tqueue();
while(1)
{
clrscr();
//displaying menu
printf(“MENU \n”);
printf(“1: insert an element in queue\n”);
printf(“2: delete an element from queue\n”);
printf(“3: display the queue\n”);
printf(“exit!\n”);
printf(“your choice:”);
scanf(“%i”,&choice);
switch(choice)
{
case 1: if(rear<4)
{
printf(“enter the no”);
scanf(“%d”,&info);
if(front==-1)
{
front=0;
rear=0;
}
else
rear=rear+1;
queue[rear]=info;
}
else
printf(“queue is full”);
break;
case 2:int info;
if(front!=-1)
{
info=queue[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else
front=front+1;
printf(“no deleted is =%d”,info);
}
else
printf(“queue is empty”);
break;
case 3: display();
break;
case 4: exit(0);
break;
default: printf(“you entered wrong choice!”);
break;
}
}
}
void initqueue()
{
//initilising front & rear to -1
front=rear=-1;
}
/*displays the current position of the queue*/
void display()
{
int i;
//displaying elements in queue
for(i=front;i<=rear;i++)
printf(“%i\n”,queue[i]);
getch();
}

 

 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

Treaps

Treaps are binary search trees in which each node has both a key and a priority.
Here’s the implementation in C:

#include<stdio.h>

#include<iostream.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>
struct btreenode
{
int data;
int priority;
struct btreenode *leftchild;
struct btreenode *rightchild;
};
struct btreenode *bt;
void insert(struct btreenode**,int,int);
void inorder(struct btreenode*);
void show(struct btreenode*);
void insertfunc();
void deletefunc();
void searchfunc();
void search(struct btreenode*,int);
void del(struct btreenode**,int);
void main()
{
int choice;
bt=NULL; //empty tree
char ch;
do
{
printf(“What operation do you wish to perform on the tree\n”);
printf(“1. Insertion\n”);
printf(“2. Deletion\n”);
printf(“3. Searching\n”);
printf(“4. Show elements\n”);
scanf(“%d”,&choice);
switch(choice)
{
case 1:
insertfunc();
break;
case 2:
deletefunc();
break;
case 3:
searchfunc();
break;
case 4:
printf(“Elements are:\n”);
show(bt);
break;
}
cout<<“\nDo you want to continue (y or n)\n”;
cin>>ch;
}while(ch==’y’||ch==’Y’);
}
void inorder(struct btreenode *sr)
{
if(sr!=NULL)
{
inorder(sr->leftchild);
inorder(sr->rightchild);
}
else
return;
}
void insertfunc()
{
int req,i=1,num,num2;
printf(“Enter the no. of items to be inserted\n”);
scanf(“%d”,&req);
while(i++<=req)
{
printf(“Enter the data\n”);
scanf(“%d”,&num);
printf(“Enter the priority\n”);
scanf(“%d”,&num2);


insert(&bt,num,num2);
}
}
void deletefunc()
{
int num;
printf(“Enter the element to be deleted\n”);
scanf(“%d”,&num);
del(&bt,num);
}
void searchfunc()
{
int num;
printf(“Enter the element to be searched\n”);
scanf(“%d”,&num);
search(bt,num);
}
void insert(struct btreenode **sr,int num,int num2)
{
if(*sr==NULL)
{
*sr=(btreenode*)malloc(sizeof(struct btreenode));
(*sr)->leftchild=NULL;
(*sr)->data=num;
(*sr)->priority=num2;
(*sr)->rightchild=NULL;
}
else
{
if(num<(*sr)->data)
insert(&((*sr)->leftchild),num,num2);
else
insert(&((*sr)->rightchild),num,num2);
}
return;
}
void search(struct  btreenode *sr,int num)
{
if(sr!=NULL)
{
search(sr->leftchild,num);
if(sr->data==num)
{
cout<<“Element found”<<endl;
return;
}
search(sr->rightchild,num);
}
else
{
return;
}
}
void del(struct btreenode **sr,int num)
{
if(*sr!=NULL)
{
del(&((*sr)->leftchild),num);
if((*sr)->data==num)
{
if((*sr)->leftchild!=NULL)
{
(*sr)=(*sr)->leftchild;
free((*sr)->leftchild);
return;
}
else
if((*sr)->rightchild!=NULL)
{
(*sr)=(*sr)->rightchild;
free(&((*sr)->rightchild));
return;
}
else
{
free(&((*sr)));
}
}
del(&((*sr)->rightchild),num);
}
}
void show(struct btreenode *sr)
{
if(sr!=NULL)
{
show(sr->leftchild);
printf(“\t%d”,sr->data);
printf(“\t%d\n”,sr->priority);
show(sr->rightchild);
}
else
return;

}

 
Leave a comment

Posted by on March 8, 2011 in C/C++