Heaps

Interface for an abstract implementation of a heap data structure.

Typedefs

typedef struct vrna_heap_s *vrna_heap_t
#include <ViennaRNA/datastructures/heap.h>

An abstract heap data structure.

See also

vrna_heap_init(), vrna_heap_free(), vrna_heap_insert(), vrna_heap_pop(), vrna_heap_top(), vrna_heap_remove(), vrna_heap_update()

typedef int (*vrna_heap_cmp_f)(const void *a, const void *b, void *data)
#include <ViennaRNA/datastructures/heap.h>

Heap compare function prototype.

Use this prototype to design the compare function for the heap implementation. The arbitrary data pointer data may be used to get access to further information required to actually compare the two values a and b.

Note

The heap implementation acts as a min-heap, therefore, the minimum element will be present at the heap’s root. In case a max-heap is required, simply reverse the logic of this compare function.

Param a:

The first object to compare

Param b:

The second object to compare

Param data:

An arbitrary data pointer passed through from the heap implementation

Return:

A value less than zero if a < b, a value greater than zero if a > b, and 0 otherwise

int() vrna_callback_heap_cmp (const void *a, const void *b, void *data)
#include <ViennaRNA/datastructures/heap.h>
typedef size_t (*vrna_heap_get_pos_f)(const void *a, void *data)
#include <ViennaRNA/datastructures/heap.h>

Retrieve the position of a particular heap entry within the heap.

Param a:

The object to look-up within the heap

Param data:

An arbitrary data pointer passed through from the heap implementation

Return:

The position of the element a within the heap, or 0 if it is not in the heap

size_t() vrna_callback_heap_get_pos (const void *a, void *data)
#include <ViennaRNA/datastructures/heap.h>
typedef void (*vrna_heap_set_pos_f)(const void *a, size_t pos, void *data)
#include <ViennaRNA/datastructures/heap.h>

Store the position of a particular heap entry within the heap.

Param a:

The object whose position shall be stored

Param pos:

The current position of a within the heap, or 0 if a was deleted

Param data:

An arbitrary data pointer passed through from the heap implementation

void() vrna_callback_heap_set_pos (const void *a, size_t pos, void *data)
#include <ViennaRNA/datastructures/heap.h>

Functions

vrna_heap_t vrna_heap_init(size_t n, vrna_heap_cmp_f cmp, vrna_heap_get_pos_f get_entry_pos, vrna_heap_set_pos_f set_entry_pos, void *data)
#include <ViennaRNA/datastructures/heap.h>

Initialize a heap data structure.

This function initializes a heap data structure. The implementation is based on a min-heap, i.e. the minimal element is located at the root of the heap. However, by reversing the logic of the compare function, one can easily transform this into a max-heap implementation.

Beside the regular operations on a heap data structure, we implement removal and update of arbitrary elements within the heap. For that purpose, however, one requires a reverse-index lookup system that, (i) for a given element stores the current position in the heap, and (ii) allows for fast lookup of an elements current position within the heap. The corresponding getter- and setter- functions may be provided through the arguments get_entry_pos and set_entry_pos, respectively.

Sometimes, it is difficult to simply compare two data structures without any context. Therefore, the compare function is provided with a user-defined data pointer that can hold any context required.

See also

vrna_heap_free(), vrna_heap_insert(), vrna_heap_pop(), vrna_heap_top(), vrna_heap_remove(), vrna_heap_update(), vrna_heap_t, vrna_heap_cmp_f, vrna_heap_get_pos_f, vrna_heap_set_pos_f

Warning

If any of the arguments get_entry_pos or set_entry_pos is NULL, the operations vrna_heap_update() and vrna_heap_remove() won’t work.

Parameters:

  • n – The initial size of the heap, i.e. the number of elements to store

  • cmp – The address of a compare function that will be used to fullfill the partial order requirement

  • get_entry_pos – The address of a function that retrieves the position of an element within the heap (or NULL)

  • set_entry_pos – The address of a function that stores the position of an element within the heap (or NULL)

  • data – An arbitrary data pointer passed through to the compare function cmp, and the set/get functions get_entry_pos / set_entry_pos

Returns:

An initialized heap data structure, or NULL on error

void vrna_heap_free(vrna_heap_t h)
#include <ViennaRNA/datastructures/heap.h>

Free memory occupied by a heap data structure.

See also

vrna_heap_init()

Parameters:

  • h – The heap that should be free’d

size_t vrna_heap_size(struct vrna_heap_s *h)
#include <ViennaRNA/datastructures/heap.h>

Get the size of a heap data structure, i.e. the number of stored elements.

Parameters:

  • h – The heap data structure

Returns:

The number of elements currently stored in the heap, or 0 upon any error

void vrna_heap_insert(vrna_heap_t h, void *v)
#include <ViennaRNA/datastructures/heap.h>

Insert an element into the heap.

See also

vrna_heap_init(), vrna_heap_pop(), vrna_heap_top(), vrna_heap_free(), vrna_heap_remove(), vrna_heap_update()

Parameters:

  • h – The heap data structure

  • v – A pointer to the object that is about to be inserted into the heap

void *vrna_heap_pop(vrna_heap_t h)
#include <ViennaRNA/datastructures/heap.h>

Pop (remove and return) the object at the root of the heap.

This function removes the root from the heap and returns it to the caller.

See also

vrna_heap_init(), vrna_heap_top(), vrna_heap_insert(), vrna_heap_free() vrna_heap_remove(), vrna_heap_update()

Parameters:

  • h – The heap data structure

Returns:

The object at the root of the heap, i.e. the minimal element (or NULL if (a) the heap is empty or (b) any error occurred)

const void *vrna_heap_top(vrna_heap_t h)
#include <ViennaRNA/datastructures/heap.h>

Get the object at the root of the heap.

See also

vrna_heap_init(), vrna_heap_pop(), vrna_heap_insert(), vrna_heap_free() vrna_heap_remove(), vrna_heap_update()

Parameters:

  • h – The heap data structure

Returns:

The object at the root of the heap, i.e. the minimal element (or NULL if (a) the heap is empty or (b) any error occurred)

void *vrna_heap_remove(vrna_heap_t h, const void *v)
#include <ViennaRNA/datastructures/heap.h>

Remove an arbitrary element within the heap.

See also

vrna_heap_init(), vrna_heap_get_pos_f, vrna_heap_set_pos_f, vrna_heap_pop(), vrna_heap_free()

Warning

This function won’t work if the heap was not properly initialized with callback functions for fast reverse-index mapping!

Parameters:

  • h – The heap data structure

  • v – The object to remove from the heap

Returns:

The object that was removed from the heap (or NULL if (a) it wasn’t found or (b) any error occurred)

void *vrna_heap_update(vrna_heap_t h, void *v)
#include <ViennaRNA/datastructures/heap.h>

Update an arbitrary element within the heap.

See also

vrna_heap_init(), vrna_heap_get_pos_f, vrna_heap_set_pos_f vrna_heap_pop(), vrna_heap_remove(), vrna_heap_free()

Note

If the object that is to be updated is not currently stored in the heap, it will be inserted. In this case, the function returns NULL.

Warning

This function won’t work if the heap was not properly initialized with callback functions for fast reverse-index mapping!

Parameters:

  • h – The heap data structure

  • v – The object to update

Returns:

The ‘previous’ object within the heap that now got replaced by v (or NULL if (a) it wasn’t found or (b) any error occurred)