Dazzle.Heap

Fields

Name

Type

Access

Description

data

str

r/w

len

int

r/w

Methods

class

new (element_size, compare_func)

extract (result)

extract_index (index_, result)

insert_vals (data, len)

ref ()

unref ()

Details

class Dazzle.Heap

Heaps are similar to a partially sorted tree but implemented as an array. They allow for efficient O(1) lookup of the highest priority item as it will always be the first item of the array.

To create a new heap use Dazzle.Heap.new().

To add items to the heap, use dzl_heap_insert_val() or Dazzle.Heap.insert_vals() to insert in bulk.

To access an item in the heap, use dzl_heap_index().

To remove an arbitrary item from the heap, use Dazzle.Heap.extract_index().

To remove the highest priority item in the heap, use Dazzle.Heap.extract().

To free a heap, use Dazzle.Heap.unref().

Here is an example that stores integers in a Dazzle.Heap:

static int
cmpint (gconstpointer a,
        gconstpointer b)
{
  return *(const gint *)a - *(const gint *)b;
}

int
main (gint   argc,
      gchar *argv[])
{
  DzlHeap *heap;
  gint i;
  gint v;

  heap = dzl_heap_new (sizeof (gint), cmpint);

  for (i = 0; i < 10000; i++)
    dzl_heap_insert_val (heap, i);
  for (i = 0; i < 10000; i++)
    dzl_heap_extract (heap, &v);

  dzl_heap_unref (heap);
}
classmethod new(element_size, compare_func)
Parameters:

  • element_size (int) – the size of each element in the heap

  • compare_func (GLib.CompareFunc) – a function to compare to elements

Returns:

A newly allocated Dazzle.Heap

Return type:

Dazzle.Heap

Creates a new Dazzle.Heap. A heap is a tree-like structure stored in an array that is not fully sorted, but head is guaranteed to be either the max, or min value based on compare_func. This is also known as a priority queue.

extract(result)
Parameters:

result (object or None) –

Return type:

bool

extract_index(index_, result)
Parameters:
Return type:

bool

insert_vals(data, len)
Parameters:
ref()
Returns:

self

Return type:

Dazzle.Heap

Increments the reference count of self by one.

unref()

Decrements the reference count of self by one, freeing the structure when the reference count reaches zero.