Overview

A heap is declared using the following overloaded macro, where T is the value's type. HEAP(T) varname;

At the core of the algorithm is a comparison function. It operates the same way as a comparison function passed to qsort(); return -1 if a is "less" than b, 1 if a is "greater" than b, and 0 if they are nominally equal. The direction of this operation determines whether this is a min-heap or a max-heap. typedef int (*comp_fn)(const void* a, const void* b, void* user_data);

void HEAP_init(HEAP* o, comp_fn cfn, void* u)

O(1)

Initializes the heap and sets the comparison function and user_data pointer. The user_data pointer is passed unchanged to the comparison function by all operations on the heap.

int HEAP_free(HEAP* o)

O(1)

Frees all internal memory, deleting the entire contents of the heap.

Operations

void HEAP_insert(HEAP* o, T* elem)

O(1) average, O(log n) worst-case

Inserts a value into the heap.

int HEAP_peek(HEAP* o, T* elem)

O(1)

Copies the most extreme value (the top of the heap) to elem without removing it from the heap. Returns 1 if the heap is empty (nothing was copied to elem), 0 otherwise.

int HEAP_peek(HEAP* o, T* elem)

O(log n)

Copies the most extreme value (the top of the heap) to elem and then removes it from the heap. Returns 1 if the heap is empty (nothing was copied to elem), 0 otherwise.

int HEAP_insert_pop(HEAP* o, T* ins, T* prev)

O(log n)

Copies the most extreme value (the top of the heap) to prev and then removes it from the heap then inserts ins into the heap. The combined operation is faster than the two operations separately. Returns 1 if the heap is empty (nothing was copied to elem), 0 otherwise.

void HEAP_delete(HEAP* o, T* elem)

O(log n)

Finds and then removes one instance of a specific element by value from the heap. The heap is assumed to not have duplicate elements, or the user must call this function once for each duplicate if all of them are to be removed.

void HEAP_find(HEAP* o, T* elem)

O(log n)

Finds and returns the internal index of the first copy of the specified element, or -1 if no copies were found. The internal index is not intended to be useful externally, only that it is different from -1.

Binary Heaps

Overview

Operations