A minheap implementation in C. Does some pointer arithmetic to achieve one-based indexing without wasting memory. API amenable to static bounds checking.

cmath.h

/*
* This file is part of cola
* Copyright (c) 2013 Gianni Tedesco
* This program is released under the terms of the GNU GPL version 3
*/
#ifndef _CMATH_H
#define _CMATH_H

#include <bits/wordsize.h>

#if __WORDSIZE == 64
# define ctz64(x) __builtin_ctzl(x)
# define ctz32(x) __builtin_ctz(x)
# define clz64(x) __builtin_clzl(x)
# define clz32(x) __builtin_clz(x)
#define log2_floor(x) log2_floor64(x)
#define log2_ciel(x) log2_ciel64(x)
#elif __WORDSIZE == 32
# define ctz64(x) __builtin_ctzll(x)
# define ctz32(x) __builtin_ctzl(x)
# define clz64(x) __builtin_clzll(x)
# define clz32(x) __builtin_clzl(x)
#define log2_floor(x) log2_floor32(x)
#define log2_ciel(x) log2_ciel32(x)
#elif __WORDSIZE == 32
#else
# error "Bad machine word size"
#endif

static inline unsigned int log2_floor64(uint64_t val)
{
	return 64 - (clz64(val) + 1);
}

static inline unsigned int log2_ceil64(uint64_t val)
{
	uint64_t ival1 = clz64(val);
	uint64_t ival2 = ival1 + 1;
	uint64_t ret = val << ival2;
	if ( ret )
		return 64 - ival1;
	else
		return 64 - ival2;
}

static inline unsigned int log2_floor32(uint32_t val)
{
	return 32 - (clz32(val) + 1);
}

static inline unsigned int log2_ceil32(uint32_t val)
{
	uint32_t ival1 = clz32(val);
	uint32_t ival2 = ival1 + 1;
	uint32_t ret = val << ival2;
	if ( ret )
		return 32 - ival1;
	else
		return 32 - ival2;
}

#endif /* _CMATH_H */

minheap.c

/*
* This file is part of cola
* Copyright (c) 2013 Gianni Tedesco
* This program is released under the terms of the GNU GPL version 3
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include <minheap.h>
#include <cmath.h>
#include <assert.h>

static unsigned long parent(unsigned long idx)
{
	return idx >> 1;
}

static unsigned long left(unsigned long idx)
{
	return idx << 1;
}

static unsigned long right(unsigned long idx)
{
	return (idx << 1) + 1;
}

static void do_sift_up(unsigned long idx, unsigned long nr_items,
				struct heap_item h[static nr_items + 1])
{
	struct heap_item tmp;
	unsigned long pidx;
	cola_key_t pv, v;

	assert(idx > 0);

	if ( idx == 1 )
		return;

	v = h[idx].key;
	pidx = parent(idx);
	pv = h[pidx].key;
	if ( pv < v )
		return;

	tmp = h[pidx];
	h[pidx] = h[idx];
	h[idx] = tmp;
	do_sift_up(pidx, nr_items, h);
}

static void do_sift_down(unsigned long idx, unsigned long nr_items,
				struct heap_item h[static nr_items + 1])
{
	unsigned long smallest, l, r;
	struct heap_item tmp;

	l = left(idx);

	if ( l > nr_items )
		return;

	r = right(idx);
	if ( r > nr_items ) {
		smallest = l;
	}else{
		smallest = (h[l].key < h[r].key) ? l : r;
	}

	if ( h[idx].key < h[smallest].key )
		return;

	tmp = h[smallest];
	h[smallest] = h[idx];
	h[idx] = tmp;
	do_sift_down(smallest, nr_items, h);
}

void minheap_init(unsigned long nr_items,
			struct heap_item h[static nr_items + 1])
{
	unsigned long lf = log2_floor64(nr_items);
	unsigned long f, c, i;

	f = (1 << lf) - 1;
	c = (1 << lf);

	for(i = f; i < nr_items; i++) {
		//printf("sift up: %"PRIu64"\n", i);
		do_sift_up(i + 1, nr_items, h);
	}

	c = (c - (nr_items - f)) >> 1;
	for(i = parent(nr_items); i < parent(nr_items) + c; i++) {
		//printf("and sift up: %"PRIu64"\n", i);
		do_sift_up(i + 1, nr_items, h);
	}
}

void minheap_sift_down(unsigned long nr_items,
				struct heap_item h[static nr_items + 1])
{
	do_sift_down(1, nr_items, h);
}

void minheap_sift_up(unsigned long nr_items,
				struct heap_item h[static nr_items + 1])
{
	do_sift_up(nr_items, nr_items, h);
}

#undef MAIN
#if MAIN
void print_heap(unsigned long nr_items,
				struct heap_item h[static nr_items + 1])
{
	unsigned long i;
	for(i = 0; i < nr_items; i++)
		printf("%"PRId64" ", h[i + 1].key);
	printf("\n");
}

int main(int argc, char **argv)
{
	unsigned long i, nr = atoi(argv[1]);
	struct heap_item *h;

	h = calloc(nr, sizeof(*h));
	h = h - 1;

	for(i = 0; i < nr; i++)
		h[i + 1].key = nr - i;
	printf("init: ");
	print_heap(nr, h);

	minheap_init(nr, h);
	printf("heapified: ");
	print_heap(nr, h);

	while(nr) {
		printf("%"PRId64": ", h[1].key);
		h[1] = h[nr--];
		minheap_sift_down(nr, h);
		print_heap(nr, h);
	}

	printf("\n");

	h[++nr].key = 100;
	minheap_sift_up(nr, h);
	print_heap(nr, h);

	h[++nr].key = 300;
	minheap_sift_up(nr, h);
	print_heap(nr, h);

	h[++nr].key = 200;
	minheap_sift_up(nr, h);
	print_heap(nr, h);

	printf("\n");
	while(nr) {
		printf("%"PRId64": ", h[1].key);
		h[1] = h[nr--];
		minheap_sift_down(nr, h);
		print_heap(nr, h);
	}
	return EXIT_SUCCESS;
}
#endif

minheap.h

/*
* This file is part of cola
* Copyright (c) 2013 Gianni Tedesco
* This program is released under the terms of the GNU GPL version 3
*/
#ifndef _MINHEAP_H
#define _MINHEAP_H

struct heap_item {
	uint64_t key;
};

void minheap_init(unsigned long nr_items,
			struct heap_item h[static nr_items + 1]);
void minheap_sift_down(unsigned long nr_items,
			struct heap_item h[static nr_items + 1]);
void minheap_sift_up(unsigned long nr_items,
			struct heap_item h[static nr_items + 1]);

#endif /* _MINHEAP_H */