binary_heap.h File Reference

This file contains the declarations for the binary min-heap used in the a* algorithm. More...

#include <stdint.h>
#include "pathfinding/maze.h"
#include <stdio.h>

Include dependency graph for binary_heap.h:

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

Go to the source code of this file.

Data Structures
struct	binary_heap
	Struct containing the binary heap. More...
struct	binary_heap_node
	This struct contains basic information about a node in a priority queue implemented with a binary heap. More...

Macros
#define	DEBUG_PRINT(...)   printf(__VA_ARGS__)
	Debug print macro. Only prints if NDEBUG is not defined. More...

Typedefs
typedef struct binary_heap_node	binary_heap_node_t
	This struct contains basic information about a node in a priority queue implemented with a binary heap. More...
typedef struct binary_heap	binary_heap_t
	Struct containing the binary heap. More...

Functions
maze_grid_cell_t *	binary_heap_delete_min (binary_heap_t *p_heap)
	Deletes and returns the root node from the binary heap. More...
uint16_t	binary_heap_get_node_idx (const binary_heap_t *p_heap, const maze_grid_cell_t *p_maze_node)
	Finds the index of a given node in the binary heap if it exists. Otherwise, returns UINT16_MAX. More...
void	binary_heap_insert (binary_heap_t *p_heap, maze_grid_cell_t *p_maze_node, uint16_t priority)
	Inserts a grid cell node into the binary heap with a given priority. More...
binary_heap_node_t	binary_heap_peek (binary_heap_t *p_heap)
	Peeks at the root node of the binary heap. More...
void	binary_heapify_down (binary_heap_t *p_heap, uint16_t index)
	Moves the node at the given index up the binary heap to maintain the heap property. This is in effect lowers the node to the correct position. More...
void	binary_heapify_up (binary_heap_t *p_heap, uint16_t index)
	Moves the node at the given index down the binary heap to maintain the heap property. This in effect raises the node to the correct position. More...

Detailed Description

This file contains the declarations for the binary min-heap used in the a* algorithm.

Author

Christopher Kok (chris.nosp@m.@for.nosp@m.celig.nosp@m.htni.nosp@m.ng.xy.nosp@m.z)

Version

0.1

Date

2023-10-12

Copyright

Copyright (c) 2023

Macro Definition Documentation

DEBUG_PRINT

#define DEBUG_PRINT

(

...

)

printf(__VA_ARGS__)

Debug print macro. Only prints if NDEBUG is not defined.

Parameters

...	Variable arguments to be printed.

Typedef Documentation

binary_heap_node_t

typedef struct binary_heap_node binary_heap_node_t

This struct contains basic information about a node in a priority queue implemented with a binary heap.

See also

binary_heap_node

binary_heap_t

typedef struct binary_heap binary_heap_t

Struct containing the binary heap.

See also

binary_heap

Warning

The array is 0-indexed, so capacity and size are always 1 greater than their respective index maximums.

Function Documentation

binary_heap_delete_min()

maze_grid_cell_t * binary_heap_delete_min

(

binary_heap_t *

p_heap

)

Deletes and returns the root node from the binary heap.

Parameters

[in,out]

p_heap

Pointer to the binary min-heap.

Returns

maze_grid_cell_t* Pointer to the original root node.

References binary_heapify_down(), binary_heap::p_array, binary_heap_node::p_maze_node, binary_heap_node::priority, and binary_heap::size.

Here is the call graph for this function:

Here is the caller graph for this function:

binary_heap_get_node_idx()

uint16_t binary_heap_get_node_idx	(	const binary_heap_t *	p_heap,
		const maze_grid_cell_t *	p_maze_node
	)

Finds the index of a given node in the binary heap if it exists. Otherwise, returns UINT16_MAX.

Parameters

[in]	p_heap	Pointer to the binary heap.
[in]	p_maze_node	Pointer to the node to be searched for.

Returns

uint16_t Index of the node if it exists, otherwise UINT16_MAX.

References binary_heap::p_array, binary_heap_node::p_maze_node, and binary_heap::size.

binary_heap_insert()

void binary_heap_insert	(	binary_heap_t *	p_heap,
		maze_grid_cell_t *	p_maze_node,
		uint16_t	priority
	)

Inserts a grid cell node into the binary heap with a given priority.

Parameters

[in,out]	p_heap	Pointer to the binary min-heap.
[in]	p_maze_node	Pointer to the grid cell node to be inserted.
[in]	priority	Priority of the node to be inserted.

References binary_heapify_up(), binary_heap::capacity, DEBUG_PRINT, binary_heap::p_array, binary_heap_node::p_maze_node, binary_heap_node::priority, and binary_heap::size.

Here is the call graph for this function:

Here is the caller graph for this function:

binary_heap_peek()

binary_heap_node_t binary_heap_peek

(

binary_heap_t *

p_heap

)

Peeks at the root node of the binary heap.

Parameters

[in]

p_heap

Pointer to the binary min-heap.

Returns

binary_heap_node_t Root node of the binary heap.

References binary_heap::p_array.

Here is the caller graph for this function:

binary_heapify_down()

void binary_heapify_down	(	binary_heap_t *	p_heap,
		uint16_t	index
	)

Moves the node at the given index up the binary heap to maintain the heap property. This is in effect lowers the node to the correct position.

Parameters

[in,out]	p_heap	Pointer to the binary heap.
[in]	index	Index of the node to be heapified down.

References binary_heap::p_array, and binary_heap_node::priority.

Here is the caller graph for this function:

binary_heapify_up()

void binary_heapify_up	(	binary_heap_t *	p_heap,
		uint16_t	index
	)

Moves the node at the given index down the binary heap to maintain the heap property. This in effect raises the node to the correct position.

Parameters

[in,out]	p_heap	Pointer to the binary heap.
[in]	index	Index of the node to be heapified up.

References binary_heap::p_array, and binary_heap_node::priority.

Here is the caller graph for this function: