heap

A binary tree based min/max heap aka priority queue. More...

Data Structures
struct	util_heap_node
	Simple node structure for binary tree, see also heap. More...
struct	util_heap
	The heap data structure, see also heap. More...

Typedefs
typedef int(*	util_heap_compar )(const void *a, const void *b)
	Comparison function that must be provided for the heap. More...

Functions
size_t	util_heap_size (unsigned int num_elements)
	Computes the size in bytes for num_elements heap entries. More...
void	util_heap_init (struct util_heap *heap, void *data, size_t size)
	Initializes a heap. More...
void *	util_heap_clear (struct util_heap *heap)
	Clear a heap heap. More...
int	util_heap_count (struct util_heap *heap)
	Returns the number of used elements in the given heap. More...
int	util_heap_enqueue (struct util_heap *heap, void *data, util_heap_compar comp)
	Add the given element to the heap. More...
void *	util_heap_dequeue (struct util_heap *heap, util_heap_compar comp)
	Remove the element with highest/lowest value from the heap. More...
void *	util_heap_first (struct util_heap *heap)
	Get the element with highest/lowest value from the heap. More...

Detailed Description

A binary tree based min/max heap aka priority queue.

The heap is a complete binary tree (all levels except the last one are full). This allows to embedd the tree nodes into an simple array and omit the left, right, parent pointers. These relations can be calculated using the zero based array index i:

• parent: p = (i - 1) div 2 (integer division = floor function)
• left: l = 2 * y + 1
• right: r = 2 * y + 2

Usage example:

#include <stdio.h>
#include <memory/memory.h>

// struct for elements to store inside the heap
struct sample_element {
    int prio;
};

// compare function for sample_element (maximum heap)
int sample_compare(const void *a, const void *b)
{
    const struct sample_element *A = a;
    const struct sample_element *B = b;

    if (A->prio < B->prio) return -1;
    if (A->prio > B->prio) return 1;
    return 0;
}

int main(void)
{
struct util_heap heap;

struct sample_element input = {2};
struct sample_element *output;

// get the size in bytes for a heap with 10 elements
int size = util_heap_size(10);

// allocte the required amount of memory
void *heapdata = ua_malloc(size);
if (heapdata == NULL) return -1;

// initialize the heap
util_heap_init(&heap, sample_compare, heapdata, size);

// add the element with priority 2
util_heap_enqueue(&heap, &input);

// remove the element with priority 2
output = util_heap_dequeue(&heap);
if (output != NULL)
    printf("dequed element with priority %i\n", output->prio);

// clear the heap structure
heapdata = util_heap_clear(&heap);

// free the memory
ua_free(heapdata);

return 0;
}

Typedef Documentation

typedef int(* util_heap_compar)(const void *a, const void *b)

Comparison function that must be provided for the heap.

Function capable of comparing the data added to heap by util_heap_enqueue. If the comparison function returns -1 for a < b the heap is a maximum heap. If you change the comparison function to return -1 for a > b the heap will become a minimum heap.

Function Documentation

void* util_heap_clear

(

struct util_heap *

heap

)

Clear a heap heap.

No furhter operations may be performed on this heap after clearing.

Returns

The data pointer that was given in util_heap_init, as it might need to be freed.

int util_heap_count

(

struct util_heap *

heap

)

Returns the number of used elements in the given heap.

void* util_heap_dequeue	(	struct util_heap *	heap,
		util_heap_compar	comp
	)

Remove the element with highest/lowest value from the heap.

Returns

The requested element or NULL if heap is empty.

int util_heap_enqueue	(	struct util_heap *	heap,
		void *	data,
		util_heap_compar	comp
	)

Add the given element to the heap.

Parameters

heap	The heap context.
data	Element to add must be suitable for util_heap_compar.

Returns

Zero on success or errocode on failure.

void* util_heap_first

(

struct util_heap *

heap

)

Get the element with highest/lowest value from the heap.

Does not remove the element.

void util_heap_init	(	struct util_heap *	heap,
		void *	data,
		size_t	size
	)

Initializes a heap.

Parameters

heap	The heap context.
comp	util_heap_compar function, determines the sort order.
data	Pointer to preallocated memory to use for the heap.
size	Size of data in bytes determined by util_heap_size.

size_t util_heap_size

(

unsigned int

num_elements

)

Computes the size in bytes for num_elements heap entries.

This can be used by the caller to allocate the correct amount of memory to be passed to util_heap_init.