binomial-heap.h File Reference

Binomial heap. More...


Defines

#define BINOMIAL_HEAP_NULL   ((void *) 0)
 A null BinomialHeapValue.

Typedefs

typedef void * BinomialHeapValue
 A value stored in a BinomialHeap.
typedef int(* BinomialHeapCompareFunc )(BinomialHeapValue value1, BinomialHeapValue value2)
 Type of function used to compare values in a binomial heap.
typedef struct _BinomialHeap BinomialHeap
 A binomial heap data structure.

Enumerations

enum  BinomialHeapType { BINOMIAL_HEAP_TYPE_MIN, BINOMIAL_HEAP_TYPE_MAX }
 Heap type. More...

Functions

BinomialHeapbinomial_heap_new (BinomialHeapType heap_type, BinomialHeapCompareFunc compare_func)
 Create a new BinomialHeap.
void binomial_heap_free (BinomialHeap *heap)
 Destroy a binomial heap.
int binomial_heap_insert (BinomialHeap *heap, BinomialHeapValue value)
 Insert a value into a binomial heap.
BinomialHeapValue binomial_heap_pop (BinomialHeap *heap)
 Remove the first value from a binomial heap.
int binomial_heap_num_entries (BinomialHeap *heap)
 Find the number of values stored in a binomial heap.


Detailed Description

Binomial heap.

A binomial heap is a heap data structure implemented using a binomial tree. In a heap, values are ordered by priority.

To create a binomial heap, use binomial_heap_new. To destroy a binomial heap, use binomial_heap_free.

To insert a value into a binomial heap, use binomial_heap_insert.

To remove the first value from a binomial heap, use binomial_heap_pop.


Typedef Documentation

Type of function used to compare values in a binomial heap.

Parameters:
value1 The first value.
value2 The second value.
Returns:
A negative number if value1 is less than value2, a positive number if value1 is greater than value2, zero if the two are equal.


Enumeration Type Documentation

Heap type.

If a heap is a min heap (BINOMIAL_HEAP_TYPE_MIN), the values with the lowest priority are stored at the top of the heap and will be the first returned. If a heap is a max heap (BINOMIAL_HEAP_TYPE_MAX), the values with the greatest priority are stored at the top of the heap.

Enumerator:
BINOMIAL_HEAP_TYPE_MIN  A minimum heap.

BINOMIAL_HEAP_TYPE_MAX  A maximum heap.


Function Documentation

void binomial_heap_free ( BinomialHeap heap  ) 

Destroy a binomial heap.

Parameters:
heap The heap to destroy.

int binomial_heap_insert ( BinomialHeap heap,
BinomialHeapValue  value 
)

Insert a value into a binomial heap.

Parameters:
heap The heap to insert into.
value The value to insert.
Returns:
Non-zero if the entry was added, or zero if it was not possible to allocate memory for the new entry.

BinomialHeap* binomial_heap_new ( BinomialHeapType  heap_type,
BinomialHeapCompareFunc  compare_func 
)

Create a new BinomialHeap.

Parameters:
heap_type The type of heap: min heap or max heap.
compare_func Pointer to a function used to compare the priority of values in the heap.
Returns:
A new binomial heap, or NULL if it was not possible to allocate the memory.

int binomial_heap_num_entries ( BinomialHeap heap  ) 

Find the number of values stored in a binomial heap.

Parameters:
heap The heap.
Returns:
The number of values in the heap.

BinomialHeapValue binomial_heap_pop ( BinomialHeap heap  ) 

Remove the first value from a binomial heap.

Parameters:
heap The heap.
Returns:
The first value in the heap, or BINOMIAL_HEAP_NULL if the heap is empty.


Generated on Sun Sep 14 03:08:02 2008 for C Algorithms by  doxygen 1.5.5