user16244012
user16244012

Reputation:

Prim's Algorithm using Priority Queue

New here and need your help. We were asked to use a priority queue and heap for Prim's algorithm and I am stuck. I know it's the shiftUp() function messing up, causing the house of cards of a program to fall down faster than the price of Coca-Cola, but I cannot put a finger on the problem. Here is my code:

 #include <stdio.h>
#define MAX 10000
typedef struct priority
{
    int edge_1st;
    int edge_2nd;
    int arr[MAX];

}pq;
pq ptr;
int insert(int);
int counter[MAX],size,cost;
void primoperate();
int extract();
int shiftUp(int);
int shiftDown(int);
int parent(int);
int leftChild(int);
int rightChild(int);
int main()
{
    int limit,add,input,j;
    printf("Enter the number of elements you want to enter");
    scanf("%d",&limit);
    for (int i=0;i<limit;i++)
    {
        printf("1st edge connected");
        scanf("%d",&ptr.edge_1st);
        printf("2nd edge connected");
        scanf("%d",&ptr.edge_2nd);
        printf("Weight of the edge");
        scanf("%d",&input);
        insert(input);
    }
    while(j<=size)
    {
        if ((counter[ptr.edge_1st]||counter[ptr.edge_2nd])!=1)
        {
            add=extract();
            printf("%d",add);
            cost+=add;
            counter[ptr.edge_1st]=counter[ptr.edge_2nd]=1;
        }
        j++;
    }
    printf("The total cost incurred after adding the weights is %d" ,cost);
}
int insert(int input)
{
    size+=1;
    ptr.arr[size]=input;
    shiftUp(size);
    printf("Added %d to the priority queue",input);
    return 0;
}
int shiftUp(int i)
{
    int temporary;
    while(i>0 && ptr.arr[parent(i)]>ptr.arr[i])
    {
        temporary=ptr.arr[parent(i)];
        ptr.arr[parent(i)]=ptr.arr[i];
        ptr.arr[i]=temporary;
        i=parent(i);
        }   
}
int parent(int i)
{
    return(i-1)/2;
}
int leftChild(int i)
{
    return ((2*i)+1);
}
int rightChild(int i)
{
    return ((2*i)+2);
}
int extract()
{
    int result=ptr.arr[0];
    printf("The topmost element in the priority queue at present is: %d",result);
    ptr.arr[0]=ptr.arr[size];
    shiftDown(0);
    return result;  
}
int shiftDown(int i)
{
    int temp=0;
    int minIndex=i;
    int left=leftChild(i);
    if(left<=size && ptr.arr[left]<ptr.arr[minIndex])
    {
        minIndex=left;
    }
    int right=rightChild(i);
    if (right <= size && ptr.arr[right] < ptr.arr[minIndex]) 
    {
        minIndex=right;
    }
    if (i != minIndex) 
    {
        temp=ptr.arr[i];
        ptr.arr[i]=ptr.arr[minIndex];
        ptr.arr[minIndex]=temp;
        shiftDown(minIndex);
    }
    
}

I know it's pretty bad and not up to your standards and all, but for my assignment, I badly need your help! Thanks in advance!

Upvotes: 0

Views: 224

Answers (0)

Related Questions