Generic heap in C

heap.c

#pragma once

#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include <limits.h>
#include <stdio.h>

typedef int (*compare_func)(void* a, void* b);

// NOTE: don't force use of pointer (or pointer-castable)?
//  instead initialize with and store the itemsize in heap and allocate memory
//  for real items/keys directly inside the heap array?
struct heap_node {
	size_t id;
	void* item;
};

struct heap {
	size_t size;
	size_t capacity;
	struct heap_node* array;
	size_t* positions;
	compare_func comparator;
};

bool heap_init(struct heap* heap, size_t capacity, compare_func compare) {
	// TODO: calloc check
	heap->size = 0;
	heap->capacity = capacity;
	heap->array = calloc(capacity, sizeof(struct heap_node));
	heap->positions = calloc(capacity, sizeof(size_t));
	heap->comparator = compare;
	return true;
}

void heap_decreased_internal(struct heap* heap, void* item, size_t id, size_t pos) {
	// while item is smaller than its parent, go up in the tree
	// we don't swap it in every step, but simply set out item in the end
	while(pos != 0 && heap->comparator(item, heap->array[pos / 2].item) < 0) {
		size_t parent_id = heap->array[pos / 2].id;
		heap->positions[id] = pos / 2;
		heap->positions[parent_id] = pos;
		heap->array[pos] = heap->array[pos / 2];
		pos /= 2;
	}

	// setting our item to the found position
	heap->positions[id] = pos;
	heap->array[pos].id = id;
	heap->array[pos].item = item;
}

void heap_increased_internal(struct heap* heap, void* item, size_t id, size_t pos) {
	// while item is greater than one of its children, swap with the smallest child
	while(2 * pos + 1 < heap->size) {  // while there is a left child
		int npos = 2 * pos + 1; // the (potential) position we go to
		if(2 * pos + 2 < heap->size) { // go to right if there is a smaller child
			npos += (heap->comparator(heap->array[npos].item, heap->array[npos + 1].item) > 0);
		}

		// only go to next pos if item is really greater
		if(heap->comparator(item, heap->array[npos].item) <= 0) {
			break;
		}

		size_t parent_id = heap->array[npos].id;
		heap->array[pos] = heap->array[npos];
		heap->positions[parent_id] = pos;
		pos = npos;
	}

	// setting our item to the found position
	heap->positions[id] = pos;
	heap->array[pos].id = id;
	heap->array[pos].item = item;
}

size_t heap_insert(struct heap* heap, void* item) {
	// TODO: check capacity

	// find id we can use, if none is empty use new one
	size_t id = heap->size;
	for(unsigned int i = 0; i < heap->size; ++i) {
		if(heap->positions[i] == (size_t) -1) {
			id = i;
			break;
		}
	}

	// starting from the last position, find the matching position
	size_t pos = heap->size;
	heap_decreased_internal(heap, item, id, pos);
	++heap->size;
	return id;
}

void heap_decreased(struct heap* heap, size_t id) {
	size_t pos = heap->positions[id];
	void* item = heap->array[pos].item;
	heap_decreased_internal(heap, item, id, pos);
}

void* heap_extract_minimum(struct heap* heap) {
	if(heap->size == 0) {
		return NULL;
	}

	// get the data from the root
	void* ret = heap->array[0].item;
	heap->positions[heap->array[0].id] = (size_t) -1;
	--heap->size;

	// move the last item to its new position starting at the root
	if(heap->size != 0) {
		struct heap_node tmp = heap->array[heap->size];
		heap_increased_internal(heap, tmp.item, tmp.id, 0);
	}

	return ret;
}

void* heap_minimum(struct heap* heap) {
	return (heap->size == 0) ? NULL : heap->array[0].item;
}

void heap_update(struct heap* heap, size_t id, void* item) {
	size_t pos = heap->positions[id];
	int c = heap->comparator(item, heap->array[pos].item);
	heap->array[pos].item = item;
	if(c < 0) {
		heap_decreased_internal(heap, item, id, pos);
	} else if(c > 0) {
		heap_increased_internal(heap, item, id, pos);
	}
}


// - testing area -
int int_compare(void* a, void* b) {
	int ia = (int)a;
	int ib = (int)b;
	return (ib < ia) - (ia < ib);
}

int main() {
	struct heap heap;
	heap_init(&heap, 100, int_compare);
	size_t i1 = heap_insert(&heap, (void*) 42);
	printf("%d\n", (int) heap_minimum(&heap));
	size_t i2 = heap_insert(&heap, (void*) 69);
	printf("%d\n", (int) heap_minimum(&heap));
	size_t i3 = heap_insert(&heap, (void*) 7);
	printf("%d\n", (int) heap_minimum(&heap));
	size_t i4 = heap_insert(&heap, (void*) 105);
	printf("%d\n", (int) heap_minimum(&heap));
	heap_update(&heap, i4, (void*) 3);
	printf("%d\n", (int) heap_extract_minimum(&heap));
	printf("%d\n", (int) heap_minimum(&heap));
	printf("%d\n", (int) heap_extract_minimum(&heap));
	printf("%d\n", (int) heap_extract_minimum(&heap));
	printf("%d\n", (int) heap_extract_minimum(&heap));
	printf("%d\n", (int) heap_extract_minimum(&heap));
	printf("%d\n", (int) heap_extract_minimum(&heap));
	return 0;

}