binary-heap.h File Reference

Binary heap. More...

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

Go to the source code of this file.

Macros
#define	BINARY_HEAP_NULL   ((void *) 0)
	A null BinaryHeapValue. More...

Typedefs
typedef void *	BinaryHeapValue
	A value stored in a BinaryHeap. More...
typedef int(*	BinaryHeapCompareFunc) (BinaryHeapValue value1, BinaryHeapValue value2)
	Type of function used to compare values in a binary heap. More...
typedef struct _BinaryHeap	BinaryHeap
	A binary heap data structure. More...

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. More...
void	binary_heap_free (BinaryHeap *heap)
	Destroy a binary heap. More...
int	binary_heap_insert (BinaryHeap *heap, BinaryHeapValue value)
	Insert a value into a binary heap. More...
BinaryHeapValue	binary_heap_pop (BinaryHeap *heap)
	Remove the first value from a binary heap. More...
int	binary_heap_num_entries (BinaryHeap *heap)
	Find the number of values stored in a binary heap. More...

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.

Definition in file binary-heap.h.

Macro Definition Documentation

BINARY_HEAP_NULL

#define BINARY_HEAP_NULL   ((void *) 0)

A null BinaryHeapValue.

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

Typedef Documentation

BinaryHeap

typedef struct _BinaryHeap BinaryHeap

A binary heap data structure.

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

BinaryHeapCompareFunc

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.

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

BinaryHeapValue

typedef void* BinaryHeapValue

A value stored in a BinaryHeap.

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

Enumeration Type Documentation

BinaryHeapType

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.

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

             {
    BINARY_HEAP_TYPE_MIN,
 
    BINARY_HEAP_TYPE_MAX
} BinaryHeapType;

Function Documentation

binary_heap_free()

void binary_heap_free

(

BinaryHeap *

heap

)

Destroy a binary heap.

Parameters

heap	The heap to destroy.

binary_heap_insert()

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.

binary_heap_new()

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.

binary_heap_num_entries()

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.

binary_heap_pop()

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.