fibonacci_heap.c File Reference

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

#include "fibonacci_heap.h"

Go to the source code of this file.

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.
void	link_trees (FibonacciHeap *heap, OrdTreeNode *child, OrdTreeNode *father)
void	swap_roots (FibonacciHeap *heap, OrdTreeNode *node1, OrdTreeNode *node2)
void	consolidate (FibonacciHeap *heap)
int	extract_min (FibonacciHeap *heap)
	Extract the minimum Node from the Fibonacci Heap.
static void	cut (FibonacciHeap *heap, OrdTreeNode *node, OrdTreeNode *parent)
static void	cascading_cut (FibonacciHeap *heap, OrdTreeNode *node)
void	decrease_value (FibonacciHeap *heap, OrdTreeNode *node, double new_value)
	Decrease the value of a Node in the Fibonacci Heap.
void	delete_node (FibonacciHeap *heap, OrdTreeNode *node)

Detailed Description

This file contains the implementation 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.c.

Function Documentation

cascading_cut()

static void cascading_cut ( FibonacciHeap *  heap, OrdTreeNode *  node  )

static

Definition at line 280 of file fibonacci_heap.c.

consolidate()

void consolidate

(

FibonacciHeap *

heap

)

Definition at line 114 of file fibonacci_heap.c.

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.

cut()

static void cut ( FibonacciHeap *  heap, OrdTreeNode *  node, OrdTreeNode *  parent  )

static

Definition at line 251 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.

delete_node()

void delete_node	(	FibonacciHeap *	heap,
		OrdTreeNode *	node
	)

Definition at line 312 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.

link_trees()

void link_trees	(	FibonacciHeap *	heap,
		OrdTreeNode *	child,
		OrdTreeNode *	father
	)

Definition at line 69 of file fibonacci_heap.c.

swap_roots()

void swap_roots	(	FibonacciHeap *	heap,
		OrdTreeNode *	node1,
		OrdTreeNode *	node2
	)

Definition at line 95 of file fibonacci_heap.c.