When I saw this amazing data structure I couldn't stop myself from trying it! I first sought resources such as this and an article about it here. It basically works as a Max-Heap and a Min-Heap at the same time. I was heavily based on these amazing Java implementations here and here.
This implementation is a macro that generates code for whichever data type you wish to work with and it is part of the C Macro Collections library currently hosted on GitHub and further to be improved when needed.
The main macro is INTERVALHEAP_GENERATE with the following parameters:
- PFX - Functions prefix
- SNAME - The struct name
- FMOD - Function modifier (currently only
staticor empty) - V - Data type you wish to work with
All you need to get started is the header intervalheap.h. Now since a question is limited to 65536 characters I had to strip down a lot of code and lines so that it could fit in this question since the macro takes a lot of characters. The code might seem a bit squished together but you can find the original code (and maybe in the future, updated) here.
intervalheap.h
#ifndef CMC_INTERVALHEAP_H
#define CMC_INTERVALHEAP_H
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define INTERVALHEAP_GENERATE(PFX, SNAME, FMOD, V) \
INTERVALHEAP_GENERATE_HEADER(PFX, SNAME, FMOD, V) \
INTERVALHEAP_GENERATE_SOURCE(PFX, SNAME, FMOD, V)
/* HEADER ********************************************************************/
#define INTERVALHEAP_GENERATE_HEADER(PFX, SNAME, FMOD, V) \
\
/* Heap Structure */ \
typedef struct SNAME##_s \
{ \
/* Dynamic array of nodes */ \
struct SNAME##_node_s *buffer; \
/* Current array capacity (how many nodes can be stored) */ \
size_t capacity; \
/* Current amount of nodes in the dynamic array */ \
size_t size; \
/* Current amount of elements in the heap */ \
size_t count; \
/* Element comparison function */ \
int (*cmp)(V, V); \
/* Function that returns an iterator to the start of the heap */ \
struct SNAME##_iter_s (*it_start)(struct SNAME##_s *); \
/* Function that returns an iterator to the end of the heap */ \
struct SNAME##_iter_s (*it_end)(struct SNAME##_s *); \
} SNAME, *SNAME##_ptr; \
\
/* Heap Node */ \
typedef struct SNAME##_node_s \
{ \
/* 0 - Value belonging to the MinHeap */ \
/* 1 - Value belonging to the MaxHeap */ \
V data[2]; \
} SNAME##_node, *SNAME##_node_ptr; \
\
/* Heap Iterator */ \
typedef struct SNAME##_iter_s \
{ \
/* Target heap */ \
struct SNAME##_s *target; \
/* Cursor's position (index) */ \
size_t cursor; \
/* If the iterator has reached the start of the iteration */ \
bool start; \
/* If the iterator has reached the end of the iteration */ \
bool end; \
} SNAME##_iter, *SNAME##_iter_ptr; \
\
FMOD SNAME *PFX##_new(size_t capacity, int (*compare)(V, V)); \
FMOD void PFX##_clear(SNAME *_heap_); \
FMOD void PFX##_free(SNAME *_heap_); \
FMOD bool PFX##_insert(SNAME *_heap_, V element); \
FMOD bool PFX##_remove_max(SNAME *_heap_, V *result); \
FMOD bool PFX##_remove_min(SNAME *_heap_, V *result); \
FMOD bool PFX##_insert_if(SNAME *_heap_, V element, bool condition); \
FMOD bool PFX##_remove_max_if(SNAME *_heap_, V *result, bool condition); \
FMOD bool PFX##_remove_min_if(SNAME *_heap_, V *result, bool condition); \
FMOD bool PFX##_update_max(SNAME *_heap_, V element); \
FMOD bool PFX##_update_min(SNAME *_heap_, V element); \
FMOD bool PFX##_max(SNAME *_heap_, V *value); \
FMOD bool PFX##_min(SNAME *_heap_, V *value); \
FMOD bool PFX##_contains(SNAME *_heap_, V element); \
FMOD bool PFX##_empty(SNAME *_heap_); \
FMOD bool PFX##_full(SNAME *_heap_); \
FMOD size_t PFX##_count(SNAME *_heap_); \
FMOD size_t PFX##_capacity(SNAME *_heap_); \
\
FMOD SNAME##_iter *PFX##_iter_new(SNAME *target); \
FMOD void PFX##_iter_free(SNAME##_iter *iter); \
FMOD void PFX##_iter_init(SNAME##_iter *iter, SNAME *target); \
FMOD bool PFX##_iter_start(SNAME##_iter *iter); \
FMOD bool PFX##_iter_end(SNAME##_iter *iter); \
FMOD void PFX##_iter_to_start(SNAME##_iter *iter); \
FMOD void PFX##_iter_to_end(SNAME##_iter *iter); \
FMOD bool PFX##_iter_next(SNAME##_iter *iter); \
FMOD bool PFX##_iter_prev(SNAME##_iter *iter); \
FMOD V PFX##_iter_value(SNAME##_iter *iter); \
FMOD size_t PFX##_iter_index(SNAME##_iter *iter); \
\
/* Default Value */ \
static inline V PFX##_impl_default_value(void) \
{ \
V _empty_value_; \
\
memset(&_empty_value_, 0, sizeof(V)); \
\
return _empty_value_; \
}
#define INTERVALHEAP_GENERATE_SOURCE(PFX, SNAME, FMOD, V) \
\
/* Implementation Detail Functions */ \
static bool PFX##_impl_grow(SNAME *_heap_); \
static void PFX##_impl_float_up_max(SNAME *_heap_); \
static void PFX##_impl_float_up_min(SNAME *_heap_); \
static void PFX##_impl_float_down_max(SNAME *_heap_); \
static void PFX##_impl_float_down_min(SNAME *_heap_); \
static SNAME##_iter PFX##_impl_it_start(SNAME *_heap_); \
static SNAME##_iter PFX##_impl_it_end(SNAME *_heap_); \
\
FMOD SNAME *PFX##_new(size_t capacity, int (*compare)(V, V)) \
{ \
SNAME *_heap_ = malloc(sizeof(SNAME)); \
if (!_heap_) \
return NULL; \
\
/* Since each node can store two elements, divide the actual capacity by 2 */ \
/* Round the capacity of nodes up */ \
capacity = capacity % 2 == 0 ? capacity / 2 : (capacity + 1) / 2; \
_heap_->buffer = malloc(sizeof(SNAME##_node) * capacity); \
\
if (!_heap_->buffer) \
{ \
free(_heap_); \
return NULL; \
} \
memset(_heap_->buffer, 0, sizeof(SNAME##_node) * capacity); \
_heap_->capacity = capacity; \
_heap_->size = 0; \
_heap_->count = 0; \
_heap_->cmp = compare; \
_heap_->it_start = PFX##_impl_it_start; \
_heap_->it_end = PFX##_impl_it_end; \
return _heap_; \
} \
\
FMOD void PFX##_clear(SNAME *_heap_) \
{ \
memset(_heap_->buffer, 0, sizeof(V) * _heap_->capacity); \
_heap_->size = 0; \
_heap_->count = 0; \
} \
\
FMOD void PFX##_free(SNAME *_heap_) \
{ \
free(_heap_->buffer); \
free(_heap_); \
} \
\
FMOD bool PFX##_insert(SNAME *_heap_, V element) \
{ \
if (PFX##_full(_heap_)) \
{ \
if (!PFX##_impl_grow(_heap_)) \
return false; \
} \
\
if (PFX##_count(_heap_) % 2 == 0) \
{ \
/* Occupying a new node */ \
_heap_->buffer[_heap_->size].data[0] = element; \
_heap_->buffer[_heap_->size].data[1] = PFX##_impl_default_value(); \
\
_heap_->size++; \
} \
else \
{ \
SNAME##_node *curr_node = &(_heap_->buffer[_heap_->size - 1]); \
\
if (_heap_->cmp(curr_node->data[0], element) > 0) \
{ \
curr_node->data[1] = curr_node->data[0]; \
curr_node->data[0] = element; \
} \
else \
{ \
curr_node->data[1] = element; \
} \
} \
\
_heap_->count++; \
\
if (PFX##_count(_heap_) <= 2) \
return true; \
\
SNAME##_node *parent = &(_heap_->buffer[(_heap_->size - 1) / 2]); \
\
if (_heap_->cmp(parent->data[0], element) > 0) \
PFX##_impl_float_up_min(_heap_); \
else if (_heap_->cmp(parent->data[1], element) < 0) \
PFX##_impl_float_up_max(_heap_); \
\
return true; \
} \
\
FMOD bool PFX##_remove_max(SNAME *_heap_, V *result) \
{ \
if (PFX##_empty(_heap_)) \
return false; \
\
if (PFX##_count(_heap_) == 1) \
{ \
*result = _heap_->buffer[0].data[0]; \
_heap_->buffer[0].data[0] = PFX##_impl_default_value(); \
_heap_->count--; \
return true; \
} \
else \
*result = _heap_->buffer[0].data[1]; \
\
SNAME##_node *last_node = &(_heap_->buffer[_heap_->size - 1]); \
\
if (PFX##_count(_heap_) % 2 == 1) \
{ \
_heap_->buffer[0].data[1] = last_node->data[0]; \
last_node->data[0] = PFX##_impl_default_value(); \
_heap_->size--; \
} \
else \
{ \
_heap_->buffer[0].data[1] = last_node->data[1]; \
\
last_node->data[1] = PFX##_impl_default_value(); \
} \
\
_heap_->count--; \
\
PFX##_impl_float_down_max(_heap_); \
\
return true; \
} \
\
FMOD bool PFX##_remove_min(SNAME *_heap_, V *result) \
{ \
if (PFX##_empty(_heap_)) \
return false; \
\
*result = _heap_->buffer[0].data[0]; \
\
if (PFX##_count(_heap_) == 1) \
{ \
_heap_->buffer[0].data[0] = PFX##_impl_default_value(); \
\
_heap_->count--; \
\
return true; \
} \
\
SNAME##_node *last_node = &(_heap_->buffer[_heap_->size - 1]); \
\
_heap_->buffer[0].data[0] = last_node->data[0]; \
\
if (PFX##_count(_heap_) % 2 == 1) \
{ \
last_node->data[0] = PFX##_impl_default_value(); \
\
_heap_->size--; \
} \
else \
{ \
last_node->data[0] = last_node->data[1]; \
last_node->data[1] = PFX##_impl_default_value(); \
} \
\
_heap_->count--; \
\
PFX##_impl_float_down_min(_heap_); \
\
return true; \
} \
\
FMOD bool PFX##_insert_if(SNAME *_heap_, V element, bool condition) \
{ \
if (condition) \
return PFX##_insert(_heap_, element); \
\
return false; \
} \
\
FMOD bool PFX##_remove_max_if(SNAME *_heap_, V *result, bool condition) \
{ \
if (condition) \
return PFX##_remove_max(_heap_, result); \
\
return false; \
} \
\
FMOD bool PFX##_remove_min_if(SNAME *_heap_, V *result, bool condition) \
{ \
if (condition) \
return PFX##_remove_min(_heap_, result); \
\
return false; \
} \
\
FMOD bool PFX##_update_max(SNAME *_heap_, V element) \
{ \
if (PFX##_empty(_heap_)) \
return false; \
\
if (PFX##_count(_heap_) == 1) \
{ \
_heap_->buffer[0].data[0] = element; \
} \
else if (_heap_->cmp(element, _heap_->buffer[0].data[0]) < 0) \
{ \
_heap_->buffer[0].data[1] = _heap_->buffer[0].data[0]; \
_heap_->buffer[0].data[0] = element; \
\
PFX##_impl_float_down_max(_heap_); \
} \
else \
{ \
_heap_->buffer[0].data[1] = element; \
\
PFX##_impl_float_down_max(_heap_); \
} \
\
return true; \
} \
\
FMOD bool PFX##_update_min(SNAME *_heap_, V element) \
{ \
if (PFX##_empty(_heap_)) \
return false; \
\
if (PFX##_count(_heap_) == 1) \
{ \
_heap_->buffer[0].data[0] = element; \
} \
else if (_heap_->cmp(element, _heap_->buffer[0].data[1]) > 0) \
{ \
_heap_->buffer[0].data[0] = _heap_->buffer[0].data[1]; \
_heap_->buffer[0].data[1] = element; \
\
PFX##_impl_float_down_min(_heap_); \
} \
else \
{ \
_heap_->buffer[0].data[0] = element; \
\
PFX##_impl_float_down_min(_heap_); \
} \
\
return true; \
} \
\
FMOD bool PFX##_max(SNAME *_heap_, V *value) \
{ \
if (PFX##_empty(_heap_)) \
return false; \
\
if (PFX##_count(_heap_) == 1) \
*value = _heap_->buffer[0].data[0]; \
else \
*value = _heap_->buffer[0].data[1]; \
\
return true; \
} \
\
FMOD bool PFX##_min(SNAME *_heap_, V *value) \
{ \
if (PFX##_empty(_heap_)) \
return false; \
\
*value = _heap_->buffer[0].data[0]; \
\
return true; \
} \
\
FMOD bool PFX##_contains(SNAME *_heap_, V element) \
{ \
for (size_t i = 0; i < _heap_->count; i++) \
{ \
if (_heap_->cmp(_heap_->buffer[i / 2].data[i % 2], element) == 0) \
return true; \
} \
\
return false; \
} \
\
FMOD bool PFX##_empty(SNAME *_heap_) \
{ \
return _heap_->count == 0; \
} \
\
FMOD bool PFX##_full(SNAME *_heap_) \
{ \
/* The heap is full if all nodes are completely filled */ \
return _heap_->size >= _heap_->capacity && _heap_->count % 2 == 0; \
} \
\
FMOD size_t PFX##_count(SNAME *_heap_) \
{ \
return _heap_->count; \
} \
\
FMOD size_t PFX##_capacity(SNAME *_heap_) \
{ \
/* Multiply by 2 since each node can store two elements */ \
return _heap_->capacity * 2; \
} \
\
FMOD SNAME##_iter *PFX##_iter_new(SNAME *target) \
{ \
SNAME##_iter *iter = malloc(sizeof(SNAME##_iter)); \
\
if (!iter) \
return NULL; \
\
PFX##_iter_init(iter, target); \
\
return iter; \
} \
\
FMOD void PFX##_iter_free(SNAME##_iter *iter) \
{ \
free(iter); \
} \
\
FMOD void PFX##_iter_init(SNAME##_iter *iter, SNAME *target) \
{ \
iter->target = target; \
iter->cursor = 0; \
iter->start = true; \
iter->end = PFX##_empty(target); \
} \
\
FMOD bool PFX##_iter_start(SNAME##_iter *iter) \
{ \
return PFX##_empty(iter->target) || iter->start; \
} \
\
FMOD bool PFX##_iter_end(SNAME##_iter *iter) \
{ \
return PFX##_empty(iter->target) || iter->end; \
} \
\
FMOD void PFX##_iter_to_start(SNAME##_iter *iter) \
{ \
iter->cursor = 0; \
iter->start = true; \
iter->end = PFX##_empty(iter->target); \
} \
\
FMOD void PFX##_iter_to_end(SNAME##_iter *iter) \
{ \
iter->cursor = iter->target->count - 1; \
iter->start = PFX##_empty(iter->target); \
iter->end = true; \
} \
\
FMOD bool PFX##_iter_next(SNAME##_iter *iter) \
{ \
if (iter->end) \
return false; \
\
iter->start = false; \
\
if (iter->cursor == iter->target->count - 1) \
iter->end = true; \
else \
iter->cursor++; \
\
return true; \
} \
\
FMOD bool PFX##_iter_prev(SNAME##_iter *iter) \
{ \
if (iter->start) \
return false; \
\
iter->end = false; \
\
if (iter->cursor == 0) \
iter->start = true; \
else \
iter->cursor--; \
\
return true; \
} \
\
FMOD V PFX##_iter_value(SNAME##_iter *iter) \
{ \
if (PFX##_empty(iter->target)) \
return PFX##_impl_default_value(); \
\
return iter->target->buffer[iter->cursor / 2].data[iter->cursor % 2]; \
} \
\
FMOD size_t PFX##_iter_index(SNAME##_iter *iter) \
{ \
return iter->cursor; \
} \
\
static bool PFX##_impl_grow(SNAME *_heap_) \
{ \
size_t new_cap = _heap_->capacity * 2; \
\
SNAME##_node *new_buffer = realloc(_heap_->buffer, sizeof(SNAME##_node) * new_cap); \
\
if (!new_buffer) \
return false; \
\
memset(new_buffer + _heap_->capacity, 0, sizeof(SNAME##_node) * _heap_->capacity); \
\
_heap_->buffer = new_buffer; \
_heap_->capacity = new_cap; \
\
return true; \
} \
\
static void PFX##_impl_float_up_max(SNAME *_heap_) \
{ \
size_t index = _heap_->size - 1; \
\
SNAME##_node *curr_node = &(_heap_->buffer[index]); \
\
while (index > 0) \
{ \
/* Parent index */ \
size_t P_index = (index - 1) / 2; \
\
SNAME##_node *parent = &(_heap_->buffer[P_index]); \
\
if (index == _heap_->size - 1 && PFX##_count(_heap_) % 2 != 0) \
{ \
if (_heap_->cmp(curr_node->data[0], parent->data[1]) < 0) \
break; \
\
V tmp = curr_node->data[0]; \
curr_node->data[0] = parent->data[1]; \
parent->data[1] = tmp; \
} \
else \
{ \
if (_heap_->cmp(curr_node->data[1], parent->data[1]) < 0) \
break; \
\
V tmp = curr_node->data[1]; \
curr_node->data[1] = parent->data[1]; \
parent->data[1] = tmp; \
} \
\
index = P_index; \
curr_node = parent; \
} \
} \
\
static void PFX##_impl_float_up_min(SNAME *_heap_) \
{ \
size_t index = _heap_->size - 1; \
SNAME##_node *curr_node = &(_heap_->buffer[index]); \
\
while (index > 0) \
{ \
size_t P_index = (index - 1) / 2; \
SNAME##_node *parent = &(_heap_->buffer[P_index]); \
\
if (_heap_->cmp(curr_node->data[0], parent->data[0]) >= 0) \
break; \
\
V tmp = curr_node->data[0]; \
curr_node->data[0] = parent->data[0]; \
parent->data[0] = tmp; \
index = P_index; \
curr_node = parent; \
} \
} \
\
static void PFX##_impl_float_down_max(SNAME *_heap_) \
{ \
size_t index = 0; \
SNAME##_node *curr_node = &(_heap_->buffer[index]); \
\
while (true) \
{ \
if (2 * index + 1 >= _heap_->size) \
break; \
\
size_t child; \
size_t L_index = index * 2 + 1; \
size_t R_index = index * 2 + 2; \
\
if (R_index < _heap_->size) \
{ \
SNAME##_node *L = &(_heap_->buffer[L_index]); \
SNAME##_node *R = &(_heap_->buffer[R_index]); \
\
if (R_index == _heap_->size - 1 && PFX##_count(_heap_) % 2 != 0) \
child = _heap_->cmp(L->data[1], R->data[0]) > 0 ? L_index : R_index; \
else \
child = _heap_->cmp(L->data[1], R->data[1]) > 0 ? L_index : R_index; \
} \
else \
child = L_index; \
\
SNAME##_node *child_node = &(_heap_->buffer[child]); \
\
if (child == _heap_->size - 1 && PFX##_count(_heap_) % 2 != 0) \
{ \
if (_heap_->cmp(curr_node->data[1], child_node->data[0]) >= 0) \
break; \
\
V tmp = child_node->data[0]; \
child_node->data[0] = curr_node->data[1]; \
curr_node->data[1] = tmp; \
} \
else \
{ \
if (_heap_->cmp(curr_node->data[1], child_node->data[1]) >= 0) \
break; \
\
V tmp = child_node->data[1]; \
child_node->data[1] = curr_node->data[1]; \
curr_node->data[1] = tmp; \
\
if (_heap_->cmp(child_node->data[0], child_node->data[1]) > 0) \
{ \
tmp = child_node->data[0]; \
child_node->data[0] = child_node->data[1]; \
child_node->data[1] = tmp; \
} \
} \
index = child; \
curr_node = child_node; \
} \
} \
\
static void PFX##_impl_float_down_min(SNAME *_heap_) \
{ \
size_t index = 0; \
\
SNAME##_node *curr_node = &(_heap_->buffer[index]); \
\
while (true) \
{ \
if (2 * index + 1 >= _heap_->size) \
break; \
\
size_t child; \
size_t L_index = index * 2 + 1; \
size_t R_index = index * 2 + 2; \
\
if (R_index < _heap_->size) \
{ \
SNAME##_node *L = &(_heap_->buffer[L_index]); \
SNAME##_node *R = &(_heap_->buffer[R_index]); \
child = _heap_->cmp(L->data[0], R->data[0]) < 0 ? L_index : R_index; \
} \
else \
child = L_index; \
\
SNAME##_node *child_node = &(_heap_->buffer[child]); \
\
if (_heap_->cmp(curr_node->data[0], child_node->data[0]) < 0) \
break; \
\
V tmp = child_node->data[0]; \
child_node->data[0] = curr_node->data[0]; \
curr_node->data[0] = tmp; \
\
if (child != _heap_->size - 1 || PFX##_count(_heap_) % 2 == 0) \
{ \
if (_heap_->cmp(child_node->data[0], child_node->data[1]) > 0) \
{ \
tmp = child_node->data[0]; \
child_node->data[0] = child_node->data[1]; \
child_node->data[1] = tmp; \
} \
} \
index = child; \
curr_node = child_node; \
} \
} \
\
static SNAME##_iter PFX##_impl_it_start(SNAME *_heap_) \
{ \
SNAME##_iter iter; \
PFX##_iter_init(&iter, _heap_); \
PFX##_iter_to_start(&iter); \
return iter; \
} \
\
static SNAME##_iter PFX##_impl_it_end(SNAME *_heap_) \
{ \
SNAME##_iter iter; \
PFX##_iter_init(&iter, _heap_); \
PFX##_iter_to_end(&iter); \
return iter; \
}
#endif /* CMC_INTERVALHEAP_H */
test.c
#include "intervalheap.h"
#include <stdio.h>
/* Generate the Interval Heap */
INTERVALHEAP_GENERATE(h, heap, , int)
/* Comparison function */
int intcmp(int a, int b)
{
return (a > b) - (a < b);
}
#define TOTAL 100
int main(void)
{
heap *my_heap = h_new(50, intcmp);
for (size_t i = 1; i <= TOTAL; i++)
{
h_insert(my_heap, i);
}
size_t half = h_count(my_heap) / 2;
for (size_t i = 0; !h_empty(my_heap); i++)
{
int r;
i < half ? h_remove_max(my_heap, &r) : h_remove_min(my_heap, &r);
printf("%d ", r);
}
h_free(my_heap);
return 0;
}
intcmpisn't very straightforward, and it would be more obvious withifs and branches. Let the compiler optimize the code \$\endgroup\$ – Cacahuete Frito Jul 6 '19 at 12:57?:unless it's for a very obvious thing. Function calls aren't very obvious things. A good place for?:is GCC's compound expression macros \$\endgroup\$ – Cacahuete Frito Jul 6 '19 at 13:02