heap.h File Reference

Heap datatype. More...

#include <datatypes/array.h>

Include dependency graph for heap.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	binary_heap(type)   dyn_array(type)
#define	heap_items(self)   array_items(self)
#define	heap_count(self)   array_count(self)
#define	heap_init(self)   array_init(self)
	Initializes an empty heap. More...
#define	heap_fini(self)   array_fini(self)
	Finalizes an heap. More...
#define	heap_is_empty(self)   array_is_empty(self)
#define	heap_min(self)   ((__typeof(*array_items(self)) const)(array_items(self)[0]))
#define	heap_insert(self, cmp_f, elem)
	Inserts an element into the heap. More...
#define	heap_extract(self, cmp_f)
	Extracts an element from the heap. More...

Detailed Description

Heap datatype.

A very simple binary heap implemented on top of our dynamic array

Copyright

Copyright (C) 2008-2021 HPDCS Group https://hpdcs.github.io

Definition in file heap.h.

Macro Definition Documentation

heap_extract

#define heap_extract	(		self,
			cmp_f
	)

Value:

__extension__({                                                         \
        __typeof(*array_items(self)) __ret_h = array_items(self)[0];    \
        __typeof(*array_items(self)) __last_h = array_pop(self);        \
        __typeof(array_count(self)) __i_h = 1U;                         \
        while (__i_h < array_count(self)) {                             \
                __i_h += __i_h + 1 < array_count(self) &&               \
                        cmp_f(                                          \
                                array_items(self)[__i_h + 1U],          \
                                array_items(self)[__i_h]                \
                        );                                              \
                if (!cmp_f(array_items(self)[__i_h], __last_h)) {       \
                        break;                                          \
                }                                                       \
                array_items(self)[(__i_h - 1U) / 2U] =                  \
                        array_items(self)[__i_h];                       \
                __i_h = __i_h * 2U + 1U;                                \
        }                                                               \
        array_items(self)[(__i_h - 1U) / 2U] = __last_h;                \
        __ret_h;                                                        \
})

Extracts an element from the heap.

Parameters

self	the heap from where to extract the element
cmp_f	a comparing function f(a, b) which returns true iff a < b

Returns

the extracted element

For correct operation of the heap you need to always pass the same cmp_f both for insertion and extraction

Definition at line 72 of file heap.h.

heap_fini

#define heap_fini

(

self

)

array_fini(self)

Finalizes an heap.

Parameters

self	the heap to finalize

The user is responsible for cleaning up the possibly contained items.

Definition at line 32 of file heap.h.

heap_init

#define heap_init

(

self

)

array_init(self)

Initializes an empty heap.

Parameters

self	the heap to initialize

Definition at line 24 of file heap.h.

heap_insert

#define heap_insert	(		self,
			cmp_f,
			elem
	)

Value:

__extension__({                                                         \
        __typeof(array_count(self)) __i_h = array_count(self);          \
        array_push(self, elem);                                         \
        while(                                                          \
                __i_h &&                                                \
                cmp_f(elem, array_items(self)[(__i_h - 1U) / 2U])       \
        ){                                                              \
                array_items(self)[__i_h] =                              \
                        array_items(self)[(__i_h - 1U) / 2U];           \
                __i_h = (__i_h - 1U) / 2U;                              \
        }                                                               \
        array_items(self)[__i_h] = elem;                                \
        __i_h;                                                          \
})

Inserts an element into the heap.

Parameters

self	the heap target of the insertion
cmp_f	a comparing function f(a, b) which returns true iff a < b
elem	the element to insert

Returns

the position of the inserted element in the underlying array

For correct operation of the heap you need to always pass the same cmp_f, both for insertion and extraction

Definition at line 47 of file heap.h.