cdata-structuresheapheapsort

Warning in C: passing argument from incompatible pointer type


I'm trying to implement extract_heap() in C. I want to pass the variable size (of the heap) as a pointer through the functions.The code is generating a few warnings as follows:

extract_max.c: In function ‘max_heapify’:
extract_max.c:26:20: warning: passing argument 2 of ‘max_heapify’ from incompatible pointer type [-Wincompatible-pointer-types]
   26 |   max_heapify(arr, &new_size, largest);
      |                    ^~~~~~~~~
      |                    |
      |                    int **
extract_max.c:6:33: note: expected ‘int *’ but argument is of type ‘int **’
    6 | void max_heapify(int *arr, int *new_size, int i)
      |                            ~~~~~^~~~~~~~
extract_max.c: In function ‘extract_max’:
extract_max.c:41:20: warning: passing argument 2 of ‘max_heapify’ from incompatible pointer type [-Wincompatible-pointer-types]
   41 |   max_heapify(arr, &size, 0);
      |                    ^~~~~
      |                    |
      |                    int **
extract_max.c:6:33: note: expected ‘int *’ but argument is of type ‘int **’
    6 | void max_heapify(int *arr, int *new_size, int i)

Also it gets compiled and produces wrong outputs. If I pass the variable size by value through functions it produces correct output just by changing size to size-1 here:

printf("\nThe elements of the heap after extract_max are:\n");  
for(int i=0; i<size-1; i++)
    printf("%d ", arr[i]);

I'm sharing full code for reproduction of outputs:

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

void max_heapify(int *arr, int *new_size, int i)
{
    int l = 2*i+1;
    int r = 2*i+2;
    int largest = i, temp;
    
    if(l<*new_size && arr[largest]<arr[l])
        largest = l;
            
    if(r<*new_size && arr[largest]<arr[r])
        largest = r;    
        
    if(largest != i)
    {
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        
        max_heapify(arr, &new_size, largest);
    }   
}

void extract_max(int *arr, int *size)
{
    int max;
    if(*size < 1)
        printf("\nNo element in the heap !");
        
    else
    {
        max = arr[0];
        arr[0] = arr[*size-1];
        *size = *size-1;
        max_heapify(arr, &size, 0);
        printf("\nThe extracted max elemnt is: %d", max);
    }   
}

int main()
{
    int i;
    int arr[] = {12, -8, 20, 2, 3, 89, 71, -6, 11, 10};
    int size = 10;
            
    //build_max heap
    for(i=size/2-1; i>=0; i--)
        max_heapify(arr, &size, i);
    
    printf("The elements of the heap after max heapification are:\n");  
    for(int i=0; i<size; i++)
        printf("%d ", arr[i]);
    printf("\n");   
        
    extract_max(arr, &size);
    
    printf("\nThe elements of the heap after extract_max are:\n");  
    for(int i=0; i<size; i++)
        printf("%d ", arr[i]);
    printf("\n");
    
    return 0;
}

Solution

  • In the function definition

    void max_heapify(int *arr, int *new_size, int i)
    

    new_size is a pointer (int *)

            ...
            max_heapify(arr, &new_size, largest);
    

    And here you are taking a pointer to it with & - so making a pointer-to-pointer (int **) while you only needed a plain pointer for the call.

    If the variable is already a pointer, do not make it more pointery, just pass it along as in:

            max_heapify(arr, new_size, largest);
    

    And similarly for the other analogous warnings.