binomial-heap.h File Reference

Binomial heap. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

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

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

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

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

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.

Definition in file binomial-heap.h.

Macro Definition Documentation

BINOMIAL_HEAP_NULL

#define BINOMIAL_HEAP_NULL   ((void *) 0)

A null BinomialHeapValue.

Definition at line 74 of file binomial-heap.h.

Typedef Documentation

BinomialHeap

typedef struct _BinomialHeap BinomialHeap

A binomial heap data structure.

Definition at line 85 of file binomial-heap.h.

BinomialHeapCompareFunc

typedef int(* BinomialHeapCompareFunc) (BinomialHeapValue value1, BinomialHeapValue value2)

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.

Definition at line 85 of file binomial-heap.h.

BinomialHeapValue

typedef void* BinomialHeapValue

A value stored in a BinomialHeap.

Definition at line 67 of file binomial-heap.h.

Enumeration Type Documentation

BinomialHeapType

enum BinomialHeapType

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.

Definition at line 53 of file binomial-heap.h.

             {
    BINOMIAL_HEAP_TYPE_MIN,
 
    BINOMIAL_HEAP_TYPE_MAX
} BinomialHeapType;

Function Documentation

binomial_heap_free()

void binomial_heap_free

(

BinomialHeap *

heap

)

Destroy a binomial heap.

Parameters

heap	The heap to destroy.

binomial_heap_insert()

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.

binomial_heap_new()

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.

binomial_heap_num_entries()

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.

binomial_heap_pop()

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.