heap.h File Reference

Interface for creating and working with heap. More...

#include "graph.h"

Go to the source code of this file.

Typedefs
typedef struct heap	Heap
	Heap is an opaque structure. More...

Functions
Heap *	heap_new_from_graph (Graph *g)
	Create new heap with nodes from given graph. More...
bool	heap_is_empty (Heap *h)
	Test if a heap is empty. More...
Node *	heap_extract_min (Heap *h)
	Remove minimal element from the heap, i.e. More...
void	heap_decrease_distance (Heap *h, Node *n, unsigned int val, Node *prev)
	Decrease distance of a certain node. More...
void	heap_free (Heap *h)
	Free all memory used by the heap. More...

Detailed Description

Interface for creating and working with heap.

This file declares functions and types for creating heaps and retrieving items from it.

Author

Lubomir Sedlar

Definition in file heap.h.

Typedef Documentation

typedef struct heap Heap

Heap is an opaque structure.

Do not access its members directly, use provided functions.

Definition at line 19 of file heap.h.

Function Documentation

void heap_decrease_distance	(	Heap *	h,
		Node *	n,
		unsigned int	val,
		Node *	prev
	)

Decrease distance of a certain node.

The val parameter is the new value of that node. It must be less then the original value. This property is tested with an assert, violating it leads to program crash.

To track the path in a graph, this function also expects previous node of the modified node. Previous node means the node from which the modified node was reached.

Parameters

h	heap to be modified
n	node that should be changed
val	new value of the node
prev	new previous node of modified node

Definition at line 123 of file heap.c.

Node* heap_extract_min

(

Heap *

h

)

Remove minimal element from the heap, i.e.

node with minimal value of dist, and return it.

Parameters

h	heap to extract from

Returns

former minimal element

Definition at line 114 of file heap.c.

void heap_free

(

Heap *

h

)

Free all memory used by the heap.

Parameters

h	heap to be freed

Definition at line 132 of file heap.c.

bool heap_is_empty

(

Heap *

h

)

Test if a heap is empty.

Parameters

h	heap to be tested

Returns

true if heap is empty, false otherwise

Definition at line 109 of file heap.c.

Heap* heap_new_from_graph

(

Graph *

g

)

Create new heap with nodes from given graph.

This function does not copy all node information, only the array of pointers to nodes. Free the allocated memory with heap_free(). All nodes in the heap are given new distance of UINT_MAX (ie. infinity) and NULL previous node.

Use heap_decrease_distance() to change distance of a node.

Parameters

g	graph to copy nodes from

Returns

newly created heap

Definition at line 89 of file heap.c.