Skip to content

Instantly share code, notes, and snippets.

@south37

south37/heap.c

Last active January 25, 2018 06:00
Show Gist options
  • Save south37/aad9d32eb705455b0247687758a892f3 to your computer and use it in GitHub Desktop.
Save south37/aad9d32eb705455b0247687758a892f3 to your computer and use it in GitHub Desktop.
Download ZIP
heap
Raw
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;
}
@south37
Copy link
Author

south37 commented Jan 25, 2018 •
edited
Loading 

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment