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

Binary heap. More...

Go to the source code of this file.

Defines
#define	BINARY_HEAP_NULL   ((void *) 0)
Typedefs
typedef void *	BinaryHeapValue
typedef int(*	BinaryHeapCompareFunc )(BinaryHeapValue value1, BinaryHeapValue value2)
typedef struct _BinaryHeap	BinaryHeap
Enumerations
enum	BinaryHeapType { BINARY_HEAP_TYPE_MIN, BINARY_HEAP_TYPE_MAX }
Functions
BinaryHeap *	binary_heap_new (BinaryHeapType heap_type, BinaryHeapCompareFunc compare_func)
void	binary_heap_free (BinaryHeap *heap)
int	binary_heap_insert (BinaryHeap *heap, BinaryHeapValue value)
BinaryHeapValue	binary_heap_pop (BinaryHeap *heap)
int	binary_heap_num_entries (BinaryHeap *heap)

---

Detailed Description

Binary heap.

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

To create a binary heap, use binary_heap_new. To destroy a binary heap, use binary_heap_free.

To insert a value into a binary heap, use binary_heap_insert.

To remove the first value from a binary heap, use binary_heap_pop.

---

Define Documentation

#define BINARY_HEAP_NULL   ((void *) 0)

A null BinaryHeapValue.

---

Typedef Documentation

typedef struct _BinaryHeap BinaryHeap

A binary heap data structure.

typedef int(* BinaryHeapCompareFunc)(BinaryHeapValue value1, BinaryHeapValue value2)

Type of function used to compare values in a binary 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* BinaryHeapValue

A value stored in a BinaryHeap.

---

Enumeration Type Documentation

enum BinaryHeapType

Heap type. If a heap is a min heap (BINARY_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 (BINARY_HEAP_TYPE_MAX), the values with the greatest priority are stored at the top of the heap.

Enumerator:

BINARY_HEAP_TYPE_MIN	A minimum heap.
BINARY_HEAP_TYPE_MAX	A maximum heap.

---

Function Documentation

void binary_heap_free

(

BinaryHeap *

heap

)

Destroy a binary heap.

Parameters:

heap

The heap to destroy.

int binary_heap_insert	(	BinaryHeap *	heap,
		BinaryHeapValue	value
	)

Insert a value into a binary 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.

BinaryHeap* binary_heap_new	(	BinaryHeapType	heap_type,
		BinaryHeapCompareFunc	compare_func
	)

Create a new BinaryHeap.

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 binary heap, or NULL if it was not possible to allocate the memory.

int binary_heap_num_entries

(

BinaryHeap *

heap

)

Find the number of values stored in a binary heap.

Parameters:

heap

The heap.

Returns:

The number of values in the heap.

BinaryHeapValue binary_heap_pop

(

BinaryHeap *

heap

)

Remove the first value from a binary heap.

Parameters:

heap

The heap.

Returns:

The first value in the heap, or BINARY_HEAP_NULL if the heap is empty.