quick heapsort implementation

heapsort.c

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

/* Heap struct (just an array and its length). */
typedef struct {
  int *slots;
  int len;
} heap_base_t, *heap_t;

/* utils */
heap_t new_heap() {
  return (heap_t) malloc(sizeof(heap_base_t));
}

void pprint(int *array, int len) {
  for(int i=0;i<=len;i++){
    printf("%d ",array[i]);
  }
  printf("\n");
}

/* Heap functions*/

/* Get the parent of any slot in the heap. */
int getparent(int index) {
  return floor((index+1)/2)-1;
}

int getleftchild(int index) {
  return (2*index)+1;
}

int getrightchild(int index) {
  return (2*index)+2;
}


/* Swap two indices in an array. */
void swap(int* array, int s1, int s2) {
  int temp = array[s1];
  array[s1] = array[s2];
  array[s2] = temp;
}

/* Reheapify an array by sifting up. */
void siftup(heap_t heap) {
  int curr = heap->len;
  int parent = getparent(heap->len);
  while (curr > 0) {
    if (heap->slots[curr] > heap->slots[parent]) {
      swap(heap->slots,curr,parent);
      curr = parent;
      parent = getparent(curr);
    } else {
      break;
    };
  }
}

/* Insert a new element in a heap. */
void insert(heap_t heap, int val) {
  /* Increment heap size by one and insert the value on the end*/
  heap->len++;
  heap->slots[heap->len] = val;
  siftup(heap);
}


/* Sift down from a given node. */
void siftdown(heap_t heap, int node) {
  int left = getleftchild(node);
  int right = getrightchild(node);
  int larger = node;
  if (left <= heap->len && heap->slots[left] > heap->slots[larger])
    larger = left;
  if (right <= heap->len && heap->slots[right] > heap->slots[larger])
    larger = right;
  /* printf("%i %i %i\n",left,right,larger); */
  if (larger != node) {
    swap(heap->slots, node, larger);
    siftdown(heap, larger);
  }
}

/* Delete the root node from the heap. */
int delete(heap_t heap) {
  int ret = heap->slots[0];
  swap(heap->slots, 0, heap->len);
  heap->len--;
  siftdown(heap,0);
  return ret;
}

/* Heapify an "heap" struct whose array
has not yet been sorted. */
void heapify(heap_t heap) {
  int i = floor(heap->len/2);
  while(i >= 0) {
    siftdown(heap, i);
    i--;
  }
}

/* Heapsort an array in place. */
void myheapsort(int* array, int len) {
  heap_t heap = new_heap();
  heap->slots = array;
  heap->len = len;
  heapify(heap);
  while(heap->len >= 0) {
    delete(heap);
  }
}

int main(int argv, char **argc) {
  int array[] = {5, 7, 7, 3, 4, 2, 3, 2, 4, 1};
  myheapsort(array,9);
  pprint(array,9);
}