fibonacci_heap.h File Reference

This file contains the declaration of the Fibonacci Heap datastructure for the Minimum Spanning Tree problem. More...

#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>
#include <float.h>
#include <math.h>

Go to the source code of this file.

Classes
struct	OrdTreeNode
	A Heap-ordered Tree Node where the key of the parent is <= the key of its children. More...
struct	FibonacciHeap
	The Fibonacci Heap datastructure as collection of Heap-ordered Trees. More...

Macros
#define	BRANCHANDBOUND1TREE_FIBONACCI_HEAP_H

Typedefs
typedef struct OrdTreeNode	OrdTreeNode
	A Heap-ordered Tree Node where the key of the parent is <= the key of its children.
typedef struct FibonacciHeap	FibonacciHeap
	The Fibonacci Heap datastructure as collection of Heap-ordered Trees.

Functions
void	create_fibonacci_heap (FibonacciHeap *heap)
	Create an empty Fibonacci Heap.
void	create_node (OrdTreeNode *node, unsigned short key, double value)
	Create a Node with a given key and value.
void	insert_node (FibonacciHeap *heap, OrdTreeNode *node)
	Insert a Node in the Fibonacci Heap.
void	create_insert_node (FibonacciHeap *heap, OrdTreeNode *node, unsigned short key, double value)
	A wrapper function to create a Node and insert it in the Fibonacci Heap.
int	extract_min (FibonacciHeap *heap)
	Extract the minimum Node from the Fibonacci Heap.
void	decrease_value (FibonacciHeap *heap, OrdTreeNode *node, double new_value)
	Decrease the value of a Node in the Fibonacci Heap.

Detailed Description

This file contains the declaration of the Fibonacci Heap datastructure for the Minimum Spanning Tree problem.

Author

Lorenzo Sciandra

Version

1.0.0 @data 2024-05-1

Copyright

Copyright (c) 2024, license MIT

Repo: https://github.com/LorenzoSciandra/GraphConvolutionalBranchandBound

Definition in file fibonacci_heap.h.

Macro Definition Documentation

BRANCHANDBOUND1TREE_FIBONACCI_HEAP_H

#define BRANCHANDBOUND1TREE_FIBONACCI_HEAP_H

Definition at line 22 of file fibonacci_heap.h.

Typedef Documentation

FibonacciHeap

typedef struct FibonacciHeap FibonacciHeap

The Fibonacci Heap datastructure as collection of Heap-ordered Trees.

OrdTreeNode

typedef struct OrdTreeNode OrdTreeNode

A Heap-ordered Tree Node where the key of the parent is <= the key of its children.

Function Documentation

create_fibonacci_heap()

void create_fibonacci_heap

(

FibonacciHeap *

heap

)

Create an empty Fibonacci Heap.

Parameters

heap	The Fibonacci Heap to be created.

Definition at line 16 of file fibonacci_heap.c.

create_insert_node()

void create_insert_node	(	FibonacciHeap *	heap,
		OrdTreeNode *	node,
		unsigned short	key,
		double	value
	)

A wrapper function to create a Node and insert it in the Fibonacci Heap.

Parameters

heap	The Fibonacci Heap where the Node will be inserted.
node	The Node to be created and inserted.
key	The key of the Node.
value	The value of the Node.

Definition at line 63 of file fibonacci_heap.c.

create_node()

void create_node	(	OrdTreeNode *	node,
		unsigned short	key,
		double	value
	)

Create a Node with a given key and value.

Parameters

node	The Node to be created.
key	The key of the Node.
value	The value of the Node.

Definition at line 25 of file fibonacci_heap.c.

decrease_value()

void decrease_value	(	FibonacciHeap *	heap,
		OrdTreeNode *	node,
		double	new_value
	)

Decrease the value of a Node in the Fibonacci Heap.

If the new value is still greater than the parent's value, nothing happens. Otherwise, the Node becomes a root. If the parent is marked, and is not a root, it becomes a root. This process is repeated until a parent is not marked or is a root.

Parameters

heap	The Fibonacci Heap where the Node is.
node	The Node whose value has to be decreased.
new_value	The new value of the Node.

Definition at line 294 of file fibonacci_heap.c.

extract_min()

int extract_min

(

FibonacciHeap *

heap

)

Extract the minimum Node from the Fibonacci Heap.

All the children of the minimum Node become new roots. The new minimum has to be found and, by doing so, the Heap is re-ordered to maintain the Heap property and minimize the height of the Heap-ordered Trees.

Parameters

heap	The Fibonacci Heap where the Node will be extracted.

Returns

The key of the minimum Node if the Heap is not empty, -1 otherwise.

Definition at line 175 of file fibonacci_heap.c.

insert_node()

void insert_node	(	FibonacciHeap *	heap,
		OrdTreeNode *	node
	)

Insert a Node in the Fibonacci Heap.

Parameters

heap	The Fibonacci Heap where the Node will be inserted.
node	The Node to be inserted.

Definition at line 38 of file fibonacci_heap.c.