main.c

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

#define HEAP_SIZE 10

typedef struct {
  int elements[HEAP_SIZE];
  int nel;
} heap;

// 1st element is at position 0
//   child is 1
//   second child is 2
// 2nd element is at position 3
//  child is 4.....
//
// thus, nth left child is at 2n + 1, nth right child at 2n + 2

int at_capacity(heap *heap) {
  return (heap->nel >= HEAP_SIZE);
}

int parent(int i, heap *heap) {
  return (int)((i - 1) / 2);
}

void insert(int n, heap *heap) {
  int cur = heap->nel;
  int par, tmp;

  if (!at_capacity(heap)) {
    heap->elements[cur] = n;
    heap->nel++;

    par = parent(cur, heap);

    // swap
    while (heap->elements[cur] < heap->elements[par]) {
      tmp = heap->elements[cur];
      heap->elements[cur] = heap->elements[par];
      heap->elements[par] = tmp;

      cur = par;
      par = parent(cur, heap);
    }
  }
}

// return index of the SMALLER child (min heap), or -1 if parent gt children
int parent_gt_children(int i, heap *heap) {
  int pos = parent(i, heap);

  // if theres a left child, and its gt parent
  if ((heap->nel > (pos + 2)) && heap->elements[pos] > heap->elements[pos + 2])
    if (heap->elements[pos+2] < heap->elements[pos+1])
      return pos+2;
    else
      return pos+1;
  else if ((heap->nel > (pos + 1)) && (heap->elements[pos] > heap->elements[pos+1]))
    return pos+1;

  return -1;
}

int extract_min(heap *heap) {
  int min, i = 0, tmp_idx, tmp;

  if (heap->nel == 0) {
    return -1;
  } else if (heap->nel == 1) {
    heap->nel--;

    return heap->elements[0];
  }

  min = heap->elements[0];
  heap->elements[0] = heap->elements[heap->nel-1];

  while (i < (heap->nel) && ((tmp_idx = parent_gt_children(i, heap)) != -1)) {
    tmp = heap->elements[i];
    heap->elements[i] = heap->elements[tmp_idx];
    heap->elements[tmp_idx] = tmp;

    i = tmp_idx;
  }

  heap->nel--;

  return min;
}


int main(int argc, char *argv[]) {
  int i;
  heap *h = malloc(sizeof(heap));
  h->nel = 0;

  int unsorted[7] = {25, 100, 36, 19, 1, 3, 17};

  insert(25, h);
  insert(100, h);
  insert(36, h);
  insert(19, h);
  insert(1, h);
  insert(3, h);
  insert(17, h);


  for (i=0;i<7;i++) {
    unsorted[i] = extract_min(h);
  }


  for (i=0;i<7;i++) {
    printf("%d\n", unsorted[i]);
  }

  return 0;
}