Binary heap (C implementation)

heap.c

// WARNING: Requires C99 compatible compiler

#include <unistd.h>
#include <stdlib.h>

#include "heap.h"

#define CMP(a, b) ((a) >= (b))

static const unsigned int base_size = 4;

// Prepares the heap for use
void heap_init(struct heap *restrict h)
{
	*h = (struct heap){
		.size = base_size,
		.count = 0,
		.data = malloc(sizeof(type) * base_size)
	};
	if (!h->data) _exit(1); // Exit if the memory allocation fails
}

// Inserts element to the heap
void heap_push(struct heap *restrict h, type value)
{
	unsigned int index, parent;

	// Resize the heap if it is too small to hold all the data
	if (h->count == h->size)
	{
		h->size <<= 1;
		h->data = realloc(h->data, sizeof(type) * h->size);
		if (!h->data) _exit(1); // Exit if the memory allocation fails
	}

	// Find out where to put the element and put it
	for(index = h->count++; index; index = parent)
	{
		parent = (index - 1) >> 1;
		if CMP(h->data[parent], value) break;
		h->data[index] = h->data[parent];
	}
	h->data[index] = value;
}

// Removes the biggest element from the heap
void heap_pop(struct heap *restrict h)
{
	unsigned int index, swap, other;

	// Remove the biggest element
	type temp = h->data[--h->count];

	// Resize the heap if it's consuming too much memory
	if ((h->count <= (h->size >> 2)) && (h->size > base_size))
	{
		h->size >>= 1;
		h->data = realloc(h->data, sizeof(type) * h->size);
		if (!h->data) _exit(1); // Exit if the memory allocation fails
	}

	// Reorder the elements
	for(index = 0; 1; index = swap)
	{
		// Find the child to swap with
		swap = (index << 1) + 1;
		if (swap >= h->count) break; // If there are no children, the heap is reordered
		other = swap + 1;
		if ((other < h->count) && CMP(h->data[other], h->data[swap])) swap = other;
		if CMP(temp, h->data[swap]) break; // If the bigger child is less than or equal to its parent, the heap is reordered

		h->data[index] = h->data[swap];
	}
	h->data[index] = temp;
}

// Heapifies a non-empty array
void heapify(type data[restrict], unsigned int count)
{
	unsigned int item, index, swap, other;
	type temp;

	// Move every non-leaf element to the right position in its subtree
	item = (count >> 1) - 1;
	while (1)
	{
		// Find the position of the current element in its subtree
		temp = data[item];
		for(index = item; 1; index = swap)
		{
			// Find the child to swap with
			swap = (index << 1) + 1;
			if (swap >= count) break; // If there are no children, the current element is positioned
			other = swap + 1;
			if ((other < count) && CMP(data[other], data[swap])) swap = other;
			if CMP(temp, data[swap]) break; // If the bigger child is smaller than or equal to the parent, the heap is reordered

			data[index] = data[swap];
		}
		if (index != item) data[index] = temp;

		if (!item) return;
		--item;
	}
}

heap.h

// WARNING: Requires C99 compatible compiler

typedef int type;

struct heap
{
	unsigned int size; // Size of the allocated memory (in number of items)
	unsigned int count; // Count of the elements in the heap
	type *data; // Array with the elements
};

void heap_init(struct heap *restrict h);
void heap_push(struct heap *restrict h, type value);
void heap_pop(struct heap *restrict h);

// Returns the biggest element in the heap
#define heap_front(h) (*(h)->data)

// Frees the allocated memory
#define heap_term(h) (free((h)->data))

void heapify(type data[restrict], unsigned int count);

I was assuming this code could work as a min-heap by just doing

define CMP(a, b) ((a) <= (b))

however, testing it out by doing this:
struct heap h;
heap_init(&h);
for (int i = 0; i < 10; i++) {
heap_push(&h, 100 - i);
}
for (int i = 0; i < 10; i++) {
printf("%d\n", h.data[i]);
}

gives me the reasonably wrong result of :

91
92
95
94
93
99
96
100
97
98

a well I see this is 4 years old, you might not be too interested ;)

whoops sry, tested another algorithm, same result, both correct offcourse because the smallest one is the first, I was assuming the whole set would have been ordered, my bad.

@NikkiKoole maybe you will try this

@NikkiKoole binary heap only promise the the first element is minimal, not that the whole list is sorted. You understood wrongly.

This code has some serious flaws.
What if someone tried to pop() an empty heap?
Or heapify() an array of length 1?
What about memory deallocation?

This code has some serious flaws.
What if someone tried to pop() an empty heap?
Or heapify() an array of length 1?
What about memory deallocation?

Totally agree. Got into that problems.

This is actually an old version but thanks for the feedback anyway.
@mucamaca Good catch about heapify() with length 1, I have actually fixed this in a later version.
about pop(), my intention when writing this was to suppose design by contract. I guess an abort() call inside pop() can be made in case the heap is empty.

Latest version is at https://gitlab.com/martinkunev/conquest_of_levidon/tree/2019/src/generic/