Skip to content

Instantly share code, notes, and snippets.

@MrThanlon
Last active August 24, 2021 03:13
Show Gist options
  • Save MrThanlon/6d30782faf81924d30f25f233b0af4d8 to your computer and use it in GitHub Desktop.
Save MrThanlon/6d30782faf81924d30f25f233b0af4d8 to your computer and use it in GitHub Desktop.
heap.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct {
size_t size;
size_t capacity;
void **elements;
char (*compare)(const void *, const void *);
} heap_t;
heap_t *heap_create(char (*compare)(const void *, const void *)) {
heap_t *res = malloc(sizeof(heap_t));
res->size = 0;
res->capacity = 1;
res->elements = malloc(sizeof(void *));
res->compare = compare;
return res;
}
void *heap_top(heap_t *heap) {
return *(heap->elements);
}
void heap_push(heap_t *heap, void *element) {
// check capacity
if (heap->size >= heap->capacity) {
// resize to 2*capacity
const size_t new_cap = heap->capacity * 2 + 1;
heap->elements = realloc(heap->elements, new_cap * sizeof(void *));
// TODO: solve failed memory allocate
heap->capacity = new_cap;
}
// push
size_t ptr = heap->size;
heap->elements[heap->size++] = element;
// heapify
while (ptr > 0) {
const size_t father = (ptr - 1) / 2;
if (heap->compare(element, heap->elements[father])) {
// swap
heap->elements[ptr] = heap->elements[father];
heap->elements[father] = element;
} else {
break;
}
ptr = father;
}
}
void heap_pop(heap_t *heap) {
if (heap->size == 0) {
// empty, do nothing
return;
}
// move the last one to the top
heap->size -= 1;
heap->elements[0] = heap->elements[heap->size];
// heapify
size_t ptr = 0;
while (ptr < heap->size) {
const size_t left_ptr = ptr * 2 + 1;
const size_t right_ptr = ptr * 2 + 2;
if (left_ptr >= heap->size) {
// no child
break;
}
void *left_child = heap->elements[left_ptr];
if (right_ptr >= heap->size) {
// no right child
if (heap->compare(left_child, heap->elements[ptr])) {
// swap left child
void *tmp = heap->elements[ptr];
heap->elements[ptr] = left_child;
heap->elements[left_ptr] = tmp;
}
break;
}
void *right_child = heap->elements[right_ptr];
if (heap->compare(heap->elements[ptr], left_child) && heap->compare(heap->elements[ptr], right_child)) {
break;
}
if (heap->compare(left_child, right_child)) {
// swap left child
void *tmp = heap->elements[ptr];
heap->elements[ptr] = left_child;
heap->elements[left_ptr] = tmp;
ptr = left_ptr;
} else {
// swap right child
void *tmp = heap->elements[ptr];
heap->elements[ptr] = right_child;
heap->elements[right_ptr] = tmp;
ptr = right_ptr;
}
}
// shrink size
if (heap->size < heap->capacity / 2) {
const size_t new_cap = heap->capacity / 2;
heap->elements = realloc(heap->elements, new_cap * sizeof(void *));
heap->capacity = new_cap;
}
}
char heap_is_empty(heap_t *heap) {
return heap->size == 0 ? 1 : 0;
}
#define TEST_RANDOM 1
char less(const void *a, const void *b) {
return (*(int *) a) < (*(int *) b) ? 1 : 0;
}
int main() {
heap_t *h = heap_create(less);
#if TEST_RANDOM
// generate random test data
srand((unsigned) time(NULL));
const int n = 10000;
int arr[n];
arr[0] = 0;
for (int i = 1; i < n; i++) {
arr[i] = rand() % 10 + arr[i - 1];
}
// print origin array
puts("Origin Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
// shuffle ptr
puts("\nShuffled array: ");
int *arr_ptr[n];
for (int i = 0; i < n; i++) {
arr_ptr[i] = &arr[i];
}
for (int i = 0; i < n; i++) {
int t = rand() % (n - i);
// swap
int *tmp = arr_ptr[i];
arr_ptr[i] = arr_ptr[i + t];
arr_ptr[i + t] = tmp;
printf("%d ", *arr_ptr[i]);
}
// heap sort
puts("\nHeap sorted: ");
for (int i = 0; i < n; i++) {
heap_push(h, arr_ptr[i]);
}
// pop and check
char is_same = 1;
for (int i = 0; i < n; i++) {
int top = *(int *) heap_top(h);
heap_pop(h);
if (top != arr[i]) {
printf("\nWrong number in index %d, got %d, expected %d\n", i, top, arr[i]);
is_same = 0;
} else {
printf("%d ", top);
}
}
if (is_same) {
puts("\nHeap works fine.");
} else {
puts("\nHeap not good.");
}
#else
int n;
scanf("%d", &n);
int arr[n];
for (int i = 0; i < n; i++) {
scanf("%d", arr + i);
heap_push(h, arr + i);
}
while (h->size) {
printf("%d ", *(int *) heap_top(h));
heap_pop(h);
}
#endif
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment