0
#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: %1f\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

  1. It takes command in the input like INSERT, DESCEND, ASCEND
  2. 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.

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

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.

5
  • 2
    Please do not post images of text (code, input, output). Copy&paste the text to the question, formatted as code blocks. Please make clear what input you use, what output you actually get and what output you would expect instead. Please explain what the problematic functions are supposed to do and what arguments get passed. I don't see an integer i in insertmaxheap. Commented Nov 10, 2021 at 13:52
  • What exactly do you mean with "the integer i does not become same with ++(*maxn)"? What arguments are passed to the function, what value do you get and what do you expect? Commented Nov 10, 2021 at 13:58
  • @Bodo oh sorry I meant the integer temp I made in the function "insertmaxheap" is not changing while *maxn is increasing. Commented Nov 10, 2021 at 14:05
  • 1
    Please edit your question to add requested information or clarification or to fix errors in your question, don't use comments for this purpose. Please add all details: What exact values do you pass to insertmaxheap? What variable(s) do you check? What value(s) do you get? What do you expect instead? BTW: When no file name has been specified the program should not continue after printing an error message. Commented Nov 10, 2021 at 14:36
  • maxn and minn is declared as (int) not (int *), however you are using *int in your functions. Commented Nov 10, 2021 at 16:02

1 Answer 1

1

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: %1f\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
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.