heap

heap.c

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

#define MAX_N 100

typedef struct {
  int nodes[MAX_N];
  int size;
} Heap;

Heap *make_empty_heap() {
  Heap *h = calloc(1, sizeof(Heap));
  h->size = 0;
  return h;
}

void heap_push(Heap *h, int new_x) {
  int i = h->size++;

  while (i > 0) {
    int p = (i - 1) / 1;

    if (h->nodes[p] <= new_x) { break; }

    h->nodes[i] = h->nodes[p];
    i           = p;
  }
  h->nodes[i] = new_x;
}

int heap_pop(Heap *h) {
  int ret = h->nodes[0];

  int x = h->nodes[--h->size];

  int i = 0;
  while (i * 2 + 1 < h->size) {
    int left = i * 2 + 1, right = i * 2 + 2;
    if (right < h->size && h->nodes[right] < h->nodes[left]) {
      left = right;
    }

    if (h->nodes[left] >= x) { break; }

    h->nodes[i] = h->nodes[left];
    i           = left;
  }
  h->nodes[i] = x;

  return ret;
}

int main() {
  Heap *heap = make_empty_heap();

  int r = 0;
  for (int i = 0; i < 1000000; ++i) {
    heap_push(heap, 3);
    heap_push(heap, 5);
    heap_push(heap, 1);
    heap_push(heap, 7);
    heap_push(heap, 10);
    heap_push(heap, 2);
    heap_push(heap, 30);
    heap_push(heap, 37);
    heap_push(heap, 11);
    heap_push(heap, 19);

    while (heap->size != 0) {
      r += heap_pop(heap);
    }
  }
  printf("%d\n", r);

  return 0;
}

vagrant@vagrant:~/rucc/tmp/c$ gcc heap.c
vagrant@vagrant:~/rucc/tmp/c$ time ./a.out
125000000

real    0m0.213s
user    0m0.208s
sys     0m0.000s

vagrant@vagrant:~/rucc/tmp/c$ rucc heap.c
vagrant@vagrant:~/rucc/tmp/c$ time ./a.out
125000000

real    0m0.677s
user    0m0.672s
sys     0m0.000s