PrevUpHomeGTS Library Reference ManualNext

Binary heaps

Name

Binary heaps -- efficient data structure for priority heaps.

Synopsis


#include <gts.h>


            GtsHeap;

GtsHeap*    gts_heap_new                    (GCompareFunc compare_func);
void        gts_heap_insert                 (GtsHeap *heap,
                                             gpointer p);
gpointer    gts_heap_remove_top             (GtsHeap *heap);
gpointer    gts_heap_top                    (GtsHeap *heap);
void        gts_heap_freeze                 (GtsHeap *heap);
void        gts_heap_thaw                   (GtsHeap *heap);
void        gts_heap_foreach                (GtsHeap *heap,
                                             GFunc func,
                                             gpointer user_data);
guint       gts_heap_size                   (GtsHeap *heap);
void        gts_heap_destroy                (GtsHeap *heap);

Description

The basic operations gts_heap_insert() and gts_heap_remove_top() are performed in O(log n) time. Calling gts_heap_freeze(), inserting elements using gts_heap_insert() and calling gts_heap_thaw() allows to build the binary heap in O(n) time.

Details

GtsHeap

typedef struct _GtsHeap GtsHeap;

An opaque data structure describing a binary heap.

gts_heap_new ()

GtsHeap*    gts_heap_new                    (GCompareFunc compare_func);

compare_func :

a GCompareFunc.

Returns :

a new GtsHeap using compare_func as a sorting function.

gts_heap_insert ()

void        gts_heap_insert                 (GtsHeap *heap,
                                             gpointer p);

Inserts a new element p in the heap.

heap :

a GtsHeap.

p :

a pointer to add to the heap.

gts_heap_remove_top ()

gpointer    gts_heap_remove_top             (GtsHeap *heap);

Removes the element at the top of the heap.

heap :

a GtsHeap.

Returns :

the element at the top of the heap.

gts_heap_top ()

gpointer    gts_heap_top                    (GtsHeap *heap);

heap :

a GtsHeap.

Returns :

the element at the top of the heap.

gts_heap_freeze ()

void        gts_heap_freeze                 (GtsHeap *heap);

Freezes the heap. Any subsequent operation will not preserve the heap property. Used in conjunction with gts_heap_insert() and gts_heap_thaw() to create a heap in O(n) time.

heap :

a GtsHeap.

gts_heap_thaw ()

void        gts_heap_thaw                   (GtsHeap *heap);

If heap has been frozen previously using gts_heap_freeze(), reorder it in O(n) time and unfreeze it.

heap :

a GtsHeap.

gts_heap_foreach ()

void        gts_heap_foreach                (GtsHeap *heap,
                                             GFunc func,
                                             gpointer user_data);

heap :

a GtsHeap.

func :

the function to call for each element in the heap.

user_data :

to pass to func.

gts_heap_size ()

guint       gts_heap_size                   (GtsHeap *heap);

heap :

a GtsHeap.

Returns :

the number of items in heap.

gts_heap_destroy ()

void        gts_heap_destroy                (GtsHeap *heap);

Free all the memory allocated for heap.

heap :

a GtsHeap.

<<< Basic Macros, functions and data structuresExtended binary heaps >>>