binary_heap.c File Reference

Source file for the binary min-heap used in the a* algorithm and floodfill algorithm. More...

#include <stddef.h>
#include <stdint.h>
#include "pathfinding/binary_heap.h"
#include "pathfinding/maze.h"

Include dependency graph for binary_heap.c:

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

Source file for the binary min-heap used in the a* algorithm and floodfill 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-11-07

Note

The functions are prefixed with binary_heap to avoid name collisions, but we are liberal with the usage of either binary_heap_ or binary_heap.

Copyright

Copyright (c) 2023

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: