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

#include "heap.h"
#include "graph-private.h"
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

Functions for creating and working with heap.

This file contains definitions of heap type and functions designed to work with it.

Author: Lubomir Sedlar

Definition in file heap.c.

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.