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
struct GtsEHeapPair
struct GtsEHeapPair {
gpointer data;
gdouble key;
guint pos;
}; |
The extended heap structure.
GtsKeyFunc ()
gdouble (*GtsKeyFunc) (gpointer item,
gpointer data); |
struct GtsEHeap
An opaque data structure describing an extended binary heap.
gts_eheap_insert ()
Inserts a new element p in the heap.
gts_eheap_insert_with_key ()
Inserts a new element p in the heap.
gts_eheap_top ()
gpointer gts_eheap_top (GtsEHeap *heap,
gdouble *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.
gts_eheap_remove ()
Removes element corresponding to p from heap in O(log n).
gts_eheap_decrease_key ()
Decreases the value of the key of the element at position p.
gts_eheap_key ()
gdouble gts_eheap_key (GtsEHeap *heap,
gpointer p); |
gts_eheap_randomized ()
void gts_eheap_randomized (GtsEHeap *heap,
gboolean randomized); |
gts_eheap_update ()
Updates the key of each element of heap and reorders it.
gts_eheap_freeze ()
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.
gts_eheap_thaw ()
If heap has been frozen previously using gts_eheap_freeze(), reorder it
in O(n) time and unfreeze it.
gts_eheap_foreach ()
void gts_eheap_foreach (GtsEHeap *heap,
GFunc func,
gpointer data); |
gts_eheap_destroy ()
void gts_eheap_destroy (GtsEHeap *heap); |
Free all the memory allocated for heap.