Search code examples
cfiletreeheapinsertion

Synchronizing data in a file and a heap by deleting values from a heap and inserting values into a heap


You write in this file on the first line, a m number, representing the number of nodes the heap can have and on the next m lines, either 1 or 2 and next to it, a specified number to use in the tree.

You have 2 operations(1 and 2): 1 is to add an element and 2 to delete the biggest one and show it.

So basically, the insertion function is tied with the heap function to insert the digit at the end and put it at front afterwards.

Also, the deletetion function with heapify is switching the first and the last number and then, deleting the last number(which is now the first), but also you need to print it in another file.

In the pla.txt file, you have something like:

12
1 18
1 12
1 3
2
1 3
1 15
2
2
1 8
2
1 19
2

12 represents the number of nodes, then if we read 1 it will do the insertion and if we read 2 it will do the deletion. My problem is that it doesn't work, it shows addresses only, in place of showing the biggest numbers. (The number 2 operation deletes the biggest number deleted in the heap, so it will input in the file "cur.txt", 18,15,12,8,19) What is wrong?

#include <stdio.h>
void swap1(int c,int b)
{
    int aux=c;
    c=b;
    b=aux;
}FILE *g=fopen("cur.txt","w");
void heapify(int a[],int index,int m)
{
    int leftindex=2*index;
    int rightindex=2*index+1;
    int father=index;
    if(leftindex<m&&leftindex>0 && a[leftindex]>a[father])
    {
        father=leftindex;
    }
    if(rightindex<m && rightindex>0&& a[rightindex]>a[father])
    {
        father=rightindex;
    }
    if(father!=index)
    {
        swap1(a[index],a[father] );
        heapify(a,father,m-1);
    }   
}
void heap(int a[], int index)
{
    int parent=(index-1)/2;
    if(a[index]>a[parent] && a[parent]>0)
    {
        swap1(a[index],a[parent]);
        heap(a,parent);
    }
}   

void insertion(int a[],int x,int  m)
{   
        m++;
        a[m-1]=x;
        heap(a,m-1);
}
void deletetion(int a[],int m)
{
    a[1]=a[m-1];
    m=m-1;  
    heapify(a,1,m); 
    fprintf(g,"%d ",a[1]);

}
int main()
{   
    FILE *f=fopen("pla.txt","r");
    int m;
    fscanf(f,"%d",&m);
    int op,x;
    int a[m];
    int z=1;
    while(fscanf(f,"%d",&op)!=EOF)
    {
        if(op==1)
        {
            fscanf(f,"%d",&x);
            insertion(a,x,z);
        }
        else 
        {
            deletetion(a,z);
        }
    }

}

Solution

  • Change fprintf(g,"%d ",&a[1]); to fprintf(g,"%d ",a[1]); in deletetion function.

    And there are some more potential errors. The main problem is that you didn't use pointer in functions. Because C does not support parameter by reference. So you need use pointer in swap function and also use pointer for parameter m for heapify, insertion and deletion functions.