Heap template implemented with dynamic array.

This file contain template macros implementing *heap* in C. The *heap* keeps its element in a known order and it can be used to implement, for example, a prioritye queue or an ordered queue.

The ordering within the heap is defined as follows:

- indexing starts from 1
- for each element with index [i] in the heap there are two descendant elements with indices [2*i] and [2*i+1],
- the heap guarantees that the descendant elements are never smaller than their parent element. Therefore it follows that there is no element smaller than element at index [1] in the rest of the heap.

Adding and removing elements to the heap is an *O(logN)* operation.

The heap array is resizeable, and it usually contain pointers to the actual entries. The template macros define two functions used to add and remove entries to the heap. The *add()* function takes the element to be added as its argument, the *remove()* function the index of the element to be removed. The template defines also a predicate used to check if the heap is full, and a function used to resize the heap.

The heap user must define four primitives:

Please note that in order to remove an entry in the heap, the application must know its index in the heap array.

The heap struct is declared with macro HEAP_DECLARE(). The prototypes for heap functions are instantiated with macro HEAP_PROTOS(). The implementation is instantiated with macro HEAP_BODIES().

Example code can be found from <su/torture_heap.c> and <sresolv/sres_cache.c>.

Definition in file heap.h.

Go to the source code of this file.

## Defines | |

#define | HEAP_BODIES(scope, heaptype, prefix, type, less, set, alloc, null) |

#define | HEAP_DECLARE(scope, heaptype, prefix, type) |

#define | HEAP_MIN_SIZE 31 |

#define | HEAP_TYPE struct { void *private; } |

Generated by Doxygen 1.6.0 Back to index