binary-heap.h File Reference

Binary heap. More...

Defines
#define	BINARY_HEAP_NULL   ((void *) 0)
	A null BinaryHeapValue.
Typedefs
typedef void *	BinaryHeapValue
	A value stored in a BinaryHeap.
typedef int(*	BinaryHeapCompareFunc )(BinaryHeapValue value1, BinaryHeapValue value2)
	Type of function used to compare values in a binary heap.
typedef struct _BinaryHeap	BinaryHeap
	A binary heap data structure.
Enumerations
enum	BinaryHeapType { BINARY_HEAP_TYPE_MIN, BINARY_HEAP_TYPE_MAX }
	Heap type. More...
Functions
BinaryHeap *	binary_heap_new (BinaryHeapType heap_type, BinaryHeapCompareFunc compare_func)
	Create a new BinaryHeap.
void	binary_heap_free (BinaryHeap *heap)
	Destroy a binary heap.
int	binary_heap_insert (BinaryHeap *heap, BinaryHeapValue value)
	Insert a value into a binary heap.
BinaryHeapValue	binary_heap_pop (BinaryHeap *heap)
	Remove the first value from a binary heap.
int	binary_heap_num_entries (BinaryHeap *heap)
	Find the number of values stored in a binary 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.

---

Typedef Documentation

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.

---

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.