/* heapsort.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define count 1
int countcmp, countintr; /* available for testing */

/* heapsort code, starting with a function prototype of a utility routine */
static void remake_heap (char *array_val, int parent_index ,int last_index, 
                         int (*compar)(), void *item_temp, int size);

void heapsort ( void *base, int nmemb, int size, int (*compar)() ){
    char *array_val = (char *)base;
    int last_parent_pos = ( nmemb - 2 ) / 2;     
    int last_parent_index = last_parent_pos;
    char *item_temp = (char *)malloc(size*sizeof(char));
    int index_val;

    /* heapsort main code */
    if(nmemb <= 1) return;

    for(index_val=last_parent_index;index_val>=0;index_val--)
        remake_heap( array_val, index_val, nmemb-1, compar, item_temp, size );
    countintr++;
    memcpy(item_temp,array_val,size); 
    memcpy(array_val,&array_val[(nmemb-1)*size],size);
    memcpy(&array_val[(nmemb-1)*size],item_temp,size);
    for(index_val=nmemb-2;index_val>0;index_val--){
      remake_heap( array_val, 0, index_val, compar, item_temp, size );
      countintr++;
      memcpy(item_temp,array_val,size); 
      memcpy(array_val,&array_val[index_val*size],size);
      memcpy(&array_val[index_val*size],item_temp,size);
    }
} /* end heapsort */

static void remake_heap (char *array_val, int parent_index ,int last_index, 
                         int (*compar)(), void *item_temp, int size) {
      int last_parent_pos = ( last_index - 1 ) / 2;     
      int last_parent_index = last_parent_pos;
      int l_child;
      int r_child;
      int max_child_index;
      int parent_temp = parent_index;

      /* code for remake_heap */
      for(;;){
        if( parent_temp > last_parent_index ) break;
        l_child = parent_temp * 2 + 1;
        if( l_child == last_index) {
          max_child_index = l_child;
        }
        else {
          r_child = l_child+1;
          countcmp++;
          if((*compar)(&array_val[l_child*size],&array_val[r_child*size])>0) {
            max_child_index = l_child;
          }
          else {
            max_child_index = r_child;
          }
        }
        countcmp++;
        if((*compar)(&array_val[max_child_index*size],
                  &array_val[parent_temp*size])>0) {
          countintr++;
          memcpy(item_temp,&array_val[max_child_index*size],size); 
          memcpy(&array_val[max_child_index*size],&array_val[parent_temp*size]
                  ,size);
          memcpy(&array_val[parent_temp*size],item_temp,size);
          parent_temp = max_child_index;
        }
        else {
          break;
        }
      }
} /* end remake_heap */