PrevUpHomeGTS Library Reference ManualNext

Extended binary heaps

Name

Extended binary heaps -- efficient data structure for priority heaps allowing removal of elements.

Synopsis


#include <gts.h>


            GtsEHeapPair;
gdouble     (*GtsKeyFunc)                   (gpointer item,
                                             gpointer data);
            GtsEHeap;

GtsEHeap*   gts_eheap_new                   (GtsKeyFunc key_func,
                                             gpointer data);
GtsEHeapPair* gts_eheap_insert              (GtsEHeap *heap,
                                             gpointer p);
GtsEHeapPair* gts_eheap_insert_with_key     (GtsEHeap *heap,
                                             gpointer p,
                                             gdouble key);
gpointer    gts_eheap_top                   (GtsEHeap *heap,
                                             gdouble *key);
gpointer    gts_eheap_remove_top            (GtsEHeap *heap,
                                             gdouble *key);
gpointer    gts_eheap_remove                (GtsEHeap *heap,
                                             GtsEHeapPair *p);
void        gts_eheap_decrease_key          (GtsEHeap *heap,
                                             GtsEHeapPair *p,
                                             gdouble new_key);
gdouble     gts_eheap_key                   (GtsEHeap *heap,
                                             gpointer p);
void        gts_eheap_randomized            (GtsEHeap *heap,
                                             gboolean randomized);
void        gts_eheap_update                (GtsEHeap *heap);
void        gts_eheap_freeze                (GtsEHeap *heap);
void        gts_eheap_thaw                  (GtsEHeap *heap);
void        gts_eheap_foreach               (GtsEHeap *heap,
                                             GFunc func,
                                             gpointer data);
guint       gts_eheap_size                  (GtsEHeap *heap);
void        gts_eheap_destroy               (GtsEHeap *heap);

Description

This data structure is similar to the binary heap implementation but adds the two operations gts_eheap_decrease_key() and gts_eheap_remove(). Contrary to the binary heap implementation, keys are stored in a GtsEHeapPair structure and comparisons between keys are performed directly (thus saving a call to a comparison function). This structure consequently provides generally faster operations at the expense of memory use. If your comparison function is simple and you don't need the extra functionalities, it is usually better to use a GtsHeap.

Details

GtsEHeapPair

typedef struct {
  gpointer data;
  gdouble key;
  guint pos;
} GtsEHeapPair;

The extended heap structure.

gpointer data;

Points to the item stored in the heap.

gdouble key;

Value of the key for this item.

guint pos;

Private field.

GtsKeyFunc ()

gdouble     (*GtsKeyFunc)                   (gpointer item,
                                             gpointer data);

item :

A pointer to an item to be stored in the heap.

data :

User data passed to gts_eheap_new().

Returns :

the value of the key for the given item.

GtsEHeap

typedef struct _GtsEHeap GtsEHeap;

An opaque data structure describing an extended binary heap.

gts_eheap_new ()

GtsEHeap*   gts_eheap_new                   (GtsKeyFunc key_func,
                                             gpointer data);

key_func :

a GtsKeyFunc or NULL.

data :

user data to be passed to key_func.

Returns :

a new GtsEHeap using key_func as key.

gts_eheap_insert ()

GtsEHeapPair* gts_eheap_insert              (GtsEHeap *heap,
                                             gpointer p);

Inserts a new element p in the heap.

heap :

a GtsEHeap.

p :

a pointer to add to the heap.

Returns :

a GtsEHeapPair describing the position of the element in the heap. This pointer is necessary for gts_eheap_remove() and gts_eheap_decrease_key().

gts_eheap_insert_with_key ()

GtsEHeapPair* gts_eheap_insert_with_key     (GtsEHeap *heap,
                                             gpointer p,
                                             gdouble key);

Inserts a new element p in the heap.

heap :

a GtsEHeap.

p :

a pointer to add to the heap.

key :

the value of the key associated to p.

Returns :

a GtsEHeapPair describing the position of the element in the heap. This pointer is necessary for gts_eheap_remove() and gts_eheap_decrease_key().

gts_eheap_top ()

gpointer    gts_eheap_top                   (GtsEHeap *heap,
                                             gdouble *key);

heap :

a GtsEHeap.

key :

a pointer on a gdouble or NULL.

Returns :

the element at the top of the heap and optionally (if key is not NULL) its key.

gts_eheap_remove_top ()

gpointer    gts_eheap_remove_top            (GtsEHeap *heap,
                                             gdouble *key);

Removes the element at the top of the heap and optionally (if key is not NULL) returns the value of its key.

heap :

a GtsEHeap.

key :

a pointer on a gdouble or NULL.

Returns :

the element at the top of the heap.

gts_eheap_remove ()

gpointer    gts_eheap_remove                (GtsEHeap *heap,
                                             GtsEHeapPair *p);

Removes element corresponding to p from heap in O(log n).

heap :

a GtsEHeap.

p :

a GtsEHeapPair.

Returns :

the element just removed from heap.

gts_eheap_decrease_key ()

void        gts_eheap_decrease_key          (GtsEHeap *heap,
                                             GtsEHeapPair *p,
                                             gdouble new_key);

Decreases the value of the key of the element at position p.

heap :

a GtsEHeap.

p :

a GtsEHeapPair.

new_key :

the new value of the key for this element. Must be smaller than the current key.

gts_eheap_key ()

gdouble     gts_eheap_key                   (GtsEHeap *heap,
                                             gpointer p);

heap :

a GtsEHeap.

p :

a pointer to be tested;

Returns :

the value of the key for pointer p.

gts_eheap_randomized ()

void        gts_eheap_randomized            (GtsEHeap *heap,
                                             gboolean randomized);

heap :

a GtsEHeap.

randomized :

whether heap should be randomized.

gts_eheap_update ()

void        gts_eheap_update                (GtsEHeap *heap);

Updates the key of each element of heap and reorders it.

heap :

a GtsEHeap.

gts_eheap_freeze ()

void        gts_eheap_freeze                (GtsEHeap *heap);

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

heap :

a GtsEHeap.

gts_eheap_thaw ()

void        gts_eheap_thaw                  (GtsEHeap *heap);

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

heap :

a GtsEHeap.

gts_eheap_foreach ()

void        gts_eheap_foreach               (GtsEHeap *heap,
                                             GFunc func,
                                             gpointer data);

heap :

a GtsEHeap.

func :

the function to call for each element in the heap.

data :

to pass to func.

gts_eheap_size ()

guint       gts_eheap_size                  (GtsEHeap *heap);

heap :

a GtsEHeap.

Returns :

the number of items in heap.

gts_eheap_destroy ()

void        gts_eheap_destroy               (GtsEHeap *heap);

Free all the memory allocated for heap.

heap :

a GtsEHeap.

<<< Binary heapsFirst In First Out heaps >>>