Reputation:
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