Making heap sort array by struct-CodePudding

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h> 

#define maxelements 1000001

typedef struct {
    int key; 
} element;

int maxn=0; 
int minn=0 ;

element maxheap[maxelements];
element minheap[maxelements]; 
element copyheap[maxelements]; 

void insertmaxheap(element item, int *maxn); 
void insertminheap(element item , int *minn); 
element deletemaxheap(int *maxn); 
element deleteminheap(int *minn); 

int main(int argc, char* argv[]){
    double start,end; 
    start= (double)clock()/CLOCKS_PER_SEC; 
//////////////////////////////////////////////////////////////
    int get,num,j ;
    int maxtemp,mintemp;
    element newitem,item;//element to print 
    char arr[8]; 
    char insert[] = "INSERT"; 
    char ascend[] = "ASCEND"; 
    char descend[] = "DESCEND"; 

    if(argc !=2) 
    {
        printf("usage: ./hw2 input_filename"); 
    }   

    FILE *fp = fopen(argv[1],"r"); 
    // FILE *result = fopen("hw2_result.txt", "w"); 
    if(fp == NULL){
        printf("The input file does not exist.\n");
    }
     
    while(!feof(fp)) {
        get = fscanf(fp,"%s %d",arr,&num); 
        if (!strcmp(arr,insert)) { //putting num into maxheap and minheap 
            printf("%d is number to insert\n", num);  
            newitem.key = num ;
            insertmaxheap(newitem, &maxn); 
            insertminheap(newitem, &minn); 
        }
        if (!strcmp(arr,ascend)) {
            //copy minheap to copyheap and then use  
            memcpy(&copyheap, &minheap,sizeof(minheap)); 
            mintemp = minn;
            printf("%d is total number and i will ascend\n", minn); 

            for(j = 0; j < minn; j  ) {
                item = deleteminheap(&minn); 
                printf("%d ",item.key);  
            }
            minn = mintemp; 
        }
        printf("\n"); 

        if (!strcmp(arr,descend)) {
            //copy maxheap to copyheap and then use
            memcpy(&copyheap,&maxheap,sizeof(maxheap)); 
            maxtemp = maxn;
            printf("%d is total number and i will descend\n", maxn); 
            for(j = 0; j < maxn; j  ) {
                item = deletemaxheap(&maxn); 
                printf("%d ",item.key );
            }

            maxn = maxtemp; 
        }
        printf("\n"); 
    }
    fclose(fp);
    end = (((double)clock()) / CLOCKS_PER_SEC);
    printf("output written to hw2_result.txt.\n"); 
    printf("running time: \n", (end-start)); 
}

void insertmaxheap(element item, int *maxn) {
    int temp; 
    temp =   (*maxn); 
    while((temp != 1) && (item.key > maxheap[temp/2].key)) {
        maxheap[temp] = maxheap[temp/2]; 
        temp /= 2; 
    }
    maxheap[temp] = item; 
    printf("i put %d in %d and %d \n",item.key, temp,*maxn);  
}

void insertminheap(element item , int *minn) {
    int i; 
    i =   (*minn);
    while((i != 1) && (item.key < minheap[i/2].key)) {
        minheap[i] = minheap[i/2]; 
        i /= 2; 
    }
    minheap[i] = item;
    printf("i put %d in %d\n", item.key,i);
}

element deletemaxheap(int *maxn) {
    //copy it to copyheap first
    int parent, child; 
    element item,temp;  
    item = copyheap[1]; 
    temp = copyheap[(*maxn)--]; 
    parent = 1;
    child = 2;  
    while(child <= *maxn) {
        if((child < *maxn) && (copyheap[child].key < copyheap[child 1].key)) child  ;
        if(temp.key >= copyheap[child].key) break;
        copyheap[parent] = copyheap[child]; 
        parent = child;
        child *= 2;  
    }
    copyheap[parent] = temp; 
    return item; 
}
element deleteminheap(int *minn){
     //copy it to copyheap first
     int parent,child; 
     parent = 1;
     child = 2 ;
     element item, temp;
     item = copyheap[1]; 
     temp = copyheap[(*minn)--]; 
     while(child <= *minn){
         if((child < *minn)&&(copyheap[child].key > copyheap[child 1].key)) child  ; 
         if(temp.key <= copyheap[child].key) break;
        copyheap[parent] = copyheap[child]; 
        parent = child; 
        child *= 2 ;
    }
    copyheap[parent] = temp;
    return item;
}

It is the code I made to get numbers from input file and make max heap , min heap. The max capacity should be 1000000 at both max heap and min heap. I think I almost made function to make those two heaps but it doesn't work well. Futhermore I made one more heap to store max and min heaps before printing out numbers that are stored. I think it is fine with the code such that

It takes command in the input like INSERT, DESCEND, ASCEND
It makes copy heap well by using memcpy function.

But I want the result to be printed 1 2 3 4 5 when command is ascend and 5 4 3 2 1 when command is descend. But here is the problem.

At the function "insertmaxheap" the integer temp does not become same with (*maxn) even though I wrote temp= (*maxn)
At the function "deleteminheap" it should print all the 5 numbers but it stops at 3 remaining 2 more numbers.

The sample input file looks like this :

INSERT 1
INSERT 2
INSERT 3
INSERT 4
INSERT 5
ASCEND
DESCEND

It is my first time to learn c programming at university but it is hard for me. I have thought about the code for whole 3 days but can not find clear solution. Due to cor-vid in Korea, I learn through online and I have to friends who can help me. Sorry for giving too much questions and codes.

CodePudding user response：

I remade your code to work:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h> 

#define MAX_ELEMENTS 1000001
typedef struct {
     int key; 
}element;
int maxn=0; 
int minn=0 ;
element maxheap[MAX_ELEMENTS];
element minheap[MAX_ELEMENTS]; 
element copyheap[MAX_ELEMENTS];

void insertmaxheap(element item, int *maxn); 
void insertminheap(element item , int *minn); 
element deletemaxheap(int *maxn); 
element deleteminheap(int *minn); 

int main(int argc, char* argv[]){
     double start,end; 
     start= (double)clock()/CLOCKS_PER_SEC; 
//////////////////////////////////////////////////////////////
     int get,num,j ;
     int maxtemp,mintemp;
     element newitem,item;//element to print 
     char arr[8]; 
     if(argc !=2) 
     {
         printf("usage: ./hw2 input_filename"); 
     }  
     FILE *fp =fopen(argv[1],"r"); 
    // FILE *result= fopen("hw2_result.txt", "w"); 
     if(fp==NULL){
         printf("The input file does not exist.\n");
     }
     
    
     while(!feof(fp)){
        get= fscanf(fp,"%s %d",arr,&num); 
         if (!strcmp(arr,"INSERT")){//putting num into maxheap and minheap 
         
            printf("%d is number to insert\n", num);  
            newitem.key=num ;
            insertmaxheap(newitem, &maxn); 
            insertminheap(newitem, &minn); 
          }
         if (!strcmp(arr,"ASCEND")){
            //copy minheap to copyheap and then use  
            memcpy(&copyheap, &minheap,sizeof(minheap)); 
            mintemp=minn;
            printf("%d is total number and i will ascend\n", minn); 
            for(j=0; j<mintemp;j  ){
                 item=deleteminheap(&minn); 
                 printf("%d ",item.key);  
            }
            printf("\nminn = %i\n", minn);
          }
          printf("\n"); 
         if (!strcmp(arr,"DESCEND")){
             //copy maxheap to copyheap and then use
             memcpy(&copyheap,&maxheap,sizeof(maxheap)); 
             maxtemp=maxn;
             printf("%d is total number and i will descend\n", maxn); 
             for(j=0;j<maxtemp;j  ){
                 item= deletemaxheap(&maxn); 
                 printf("%d ",item.key );
             }
             printf("\nmaxn: %d\n", maxn);
          }
          printf("\n"); 
     }
     fclose(fp);
     end=(((double)clock())/CLOCKS_PER_SEC);
     printf("output written to hw2_result.txt.\n"); 
     printf("running time: \n", (end-start)); 
}
void insertmaxheap(element item, int *maxn){
     int temp; 
     temp=*maxn; 
     (*maxn)  ;
      while((temp!=0)&&(item.key>maxheap[temp/2].key)){
         maxheap[temp]=maxheap[temp/2]; 
         temp/=2; 
      }
      maxheap[temp]=item; 
      printf("i put %d in %d and %d \n",item.key, temp,*maxn);  
}
void insertminheap(element item , int *minn){
     int i; 
     i=*minn;
       (*minn);
     while((i!=0)&&(item.key<minheap[i/2].key)){
         minheap[i]=minheap[i/2]; 
         i/=2; 
     }
     minheap[i]=item;
         printf("i put %d in %d\n", item.key,i);
}
element deletemaxheap(int *maxn){
     //copy it to copyheap first
     int parent, child; 
     element item,temp;  
     item=copyheap[0]; 
     temp=copyheap[*maxn]; 
     (*maxn)--;
     parent=0;
     child=1;  
     while(child<=*maxn){
         if((child<*maxn)&&(copyheap[child].key<copyheap[child 1].key))child  ;
         if(temp.key>=copyheap[child].key){
             break;
         }
         copyheap[parent]=copyheap[child]; 
         parent=child;
         child*=2;  
     }
     copyheap[parent]=temp; 
     return item; 
}
element deleteminheap(int *minn){
     //copy it to copyheap first
     int parent,child; 
     parent=0;
     child=1 ;
     element item,temp;
     item = copyheap[0]; 
     temp= copyheap[(*minn)-1]; 
     (*minn)--;
     while(child<=*minn){
         if((child<*minn)&&(copyheap[child].key>copyheap[child 1].key))child  ; 
         if(temp.key<=copyheap[child].key)break;
         copyheap[parent]=copyheap[child]; 
         parent=child; 
         child*=2 ;
     }
     copyheap[parent]=temp;
     return item;
}

I made sure that both arrays start from index 0 instead of 1, that's why variable tmp reaches this time 0, not 1.

To answer your first question:

variable tmp gets divided by two as long as it reaches 0 (1 previously).

To answer your second question:

Your sorting algorithm for maxheap really works but for minheap there is an issue. It runs out of memory range (out of `copyheap` array). That's why it didn't print all of the numbers.

I changed your code here and there to make it more visible for me. Hopefully, it will not confuse you.

If you have more questions about this code write them down, I will be glad to answer. I'm student too so i have some experience in correcting other student's messy code so feel free to ask ;D