/cvmfs/atlas.cern.ch/repo/sw/ASG/AnalysisBase/2.4.30/CxxUtils/CxxUtils/libcalg/binomial-heap.h File Reference

Binomial heap. More...

Go to the source code of this file.

Defines
#define	BINOMIAL_HEAP_NULL   ((void *) 0)
Typedefs
typedef void *	BinomialHeapValue
typedef int(*	BinomialHeapCompareFunc )(BinomialHeapValue value1, BinomialHeapValue value2)
typedef struct _BinomialHeap	BinomialHeap
Enumerations
enum	BinomialHeapType { BINOMIAL_HEAP_TYPE_MIN, BINOMIAL_HEAP_TYPE_MAX }
Functions
BinomialHeap *	binomial_heap_new (BinomialHeapType heap_type, BinomialHeapCompareFunc compare_func)
void	binomial_heap_free (BinomialHeap *heap)
int	binomial_heap_insert (BinomialHeap *heap, BinomialHeapValue value)
BinomialHeapValue	binomial_heap_pop (BinomialHeap *heap)
int	binomial_heap_num_entries (BinomialHeap *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.

---

Define Documentation

#define BINOMIAL_HEAP_NULL   ((void *) 0)

A null BinomialHeapValue.

---

Typedef Documentation

typedef struct _BinomialHeap BinomialHeap

A binomial heap data structure.

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.

typedef void* BinomialHeapValue

A value stored in a BinomialHeap.

---

Enumeration Type Documentation

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.

---

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.