Posted on by Kalkicode
Code Heap

Simplest node insertion of Fibonacci Heap

Here given code implementation process.

/*
  Java program
  Simplest node insertion of Fibonacci Heap 
*/
class HeapNode
{
    public HeapNode left;
    public HeapNode right;
    public int key;
    public HeapNode(int value)
    {
        key = value;
        left = null;
        right = null;
    }
}
public class FibonacciHeap
{
    // This is use to store information of number of nodes in heap
    private int size;
    private HeapNode root;
    public FibonacciHeap()
    {
        root = null;
        size = 0;
    }
    // Simplest method of node insertion of Fibonacci min Heap
    public void insert(int value)
    {
        HeapNode node = new HeapNode(value);
        // Set initial node pointer
        // This is similar to circular doubly linked list
        node.left = node;
        node.right = node;
        if (this.root == null)
        {
            // When insert first node
            this.root = node;
        }
        else
        {
            this.root.left.right = node;
            node.right = this.root;
            node.left = this.root.left;
            this.root.left = node;
            if (this.root.key > node.key)
            {
                // Make new root
                this.root = node;
            }
        }
        this.size++;
    }
    // Display element of tree
    public void dispaly()
    {
        if (this.root == null)
        {
            System.out.println("Empty Tree");
        }
        else
        {
            // Display root value
            System.out.print("  " + this.root.key);

            HeapNode head = this.root.right;

            // Display other element
            while(head != null && head != root) 
            {
                // Display node value
                System.out.print("  " + head.key);

                // visit to right node
                head = head.right;
            } 
        }
    }
    public int totalNode()
    {
        return this.size;
    }
    public static void main(String[] args)
    {
        FibonacciHeap heap = new FibonacciHeap();
        //Construct Tree
        heap.insert(5);
        heap.insert(7);
        heap.insert(4);
        heap.insert(3);
        heap.insert(9);
        heap.insert(14);
        heap.insert(2);
        heap.insert(1);
        heap.insert(6);
        heap.insert(11);
        // Display number of nodes
        System.out.print("\n Total Nodes : " + heap.totalNode() + "\n");
        // Display node values
        heap.dispaly();
    }
}

Output

 Total Nodes : 10
  1  2  3  4  5  7  9  14  6  11
// Include header file
#include <iostream>
using namespace std;
/*
  C++ program
  Simplest node insertion of Fibonacci Heap 
*/
class HeapNode
{
	public: 
    HeapNode *left;
	HeapNode *right;
	int key;
	HeapNode(int value)
	{
		this->key = value;
		this->left = NULL;
		this->right = NULL;
	}
};
class FibonacciHeap
{
	public:
	// This is use to store information of number of nodes in heap
	int size;
	HeapNode *root;
	FibonacciHeap()
	{
		this->root = NULL;
		this->size = 0;
	}
	// Simplest method of node insertion of Fibonacci min Heap
	void insert(int value)
	{
		HeapNode *node = new HeapNode(value);
		// Set initial node pointer
		// This is similar to circular doubly linked list
		node->left = node;
		node->right = node;
		if (this->root == NULL)
		{
			// When insert first node
			this->root = node;
		}
		else
		{
			this->root->left->right = node;
			node->right = this->root;
			node->left = this->root->left;
			this->root->left = node;
			if (this->root->key > node->key)
			{
				// Make new root
				this->root = node;
			}
		}
		this->size++;
	}
	// Display element of tree
	void dispaly()
	{
		if (this->root == NULL)
		{
			cout << "Empty Tree" << endl;
		}
		else
		{
			// Display root value
			cout << "  " << this->root->key;
			HeapNode *head = this->root->right;
			// Display other element
			while (head != NULL && head != this->root)
			{
				// Display node value
				cout << "  " << head->key;
				// visit to right node
				head = head->right;
			}
		}
	}
	int totalNode()
	{
		return this->size;
	}
};
int main()
{
	FibonacciHeap *heap = new FibonacciHeap();
	//Construct Tree
	heap->insert(5);
	heap->insert(7);
	heap->insert(4);
	heap->insert(3);
	heap->insert(9);
	heap->insert(14);
	heap->insert(2);
	heap->insert(1);
	heap->insert(6);
	heap->insert(11);
	// Display number of nodes
	cout << "\n Total Nodes : " << heap->totalNode() << "\n";
	// Display node values
	heap->dispaly();
	return 0;
}

Output

 Total Nodes : 10
  1  2  3  4  5  7  9  14  6  11
// Include namespace system
using System;
/*
  Csharp program
  Simplest node insertion of Fibonacci Heap 
*/
public class HeapNode
{
	public HeapNode left;
	public HeapNode right;
	public int key;
	public HeapNode(int value)
	{
		this.key = value;
		this.left = null;
		this.right = null;
	}
}
public class FibonacciHeap
{
	// This is use to store information of number of nodes in heap
	private int size;
	private HeapNode root;
	public FibonacciHeap()
	{
		this.root = null;
		this.size = 0;
	}
	// Simplest method of node insertion of Fibonacci min Heap
	public void insert(int value)
	{
		HeapNode node = new HeapNode(value);
		// Set initial node pointer
		// This is similar to circular doubly linked list
		node.left = node;
		node.right = node;
		if (this.root == null)
		{
			// When insert first node
			this.root = node;
		}
		else
		{
			this.root.left.right = node;
			node.right = this.root;
			node.left = this.root.left;
			this.root.left = node;
			if (this.root.key > node.key)
			{
				// Make new root
				this.root = node;
			}
		}
		this.size++;
	}
	// Display element of tree
	public void dispaly()
	{
		if (this.root == null)
		{
			Console.WriteLine("Empty Tree");
		}
		else
		{
			// Display root value
			Console.Write("  " + this.root.key);
			HeapNode head = this.root.right;
			// Display other element
			while (head != null && head != this.root)
			{
				// Display node value
				Console.Write("  " + head.key);
				// visit to right node
				head = head.right;
			}
		}
	}
	public int totalNode()
	{
		return this.size;
	}
	public static void Main(String[] args)
	{
		FibonacciHeap heap = new FibonacciHeap();
		//Construct Tree
		heap.insert(5);
		heap.insert(7);
		heap.insert(4);
		heap.insert(3);
		heap.insert(9);
		heap.insert(14);
		heap.insert(2);
		heap.insert(1);
		heap.insert(6);
		heap.insert(11);
		// Display number of nodes
		Console.Write("\n Total Nodes : " + heap.totalNode() + "\n");
		// Display node values
		heap.dispaly();
	}
}

Output

 Total Nodes : 10
  1  2  3  4  5  7  9  14  6  11
package main
import "fmt"
/*
  Go program
  Simplest node insertion of Fibonacci Heap 
*/
type HeapNode struct {
	left * HeapNode
	right * HeapNode
	key int
}
func getHeapNode(value int) * HeapNode {
	var me *HeapNode = &HeapNode {}
	me.key = value
	me.left = nil
	me.right = nil
	return me
}
type FibonacciHeap struct {
	// This is use to store information of number of nodes in heap
	size int
	root * HeapNode
}
func getFibonacciHeap() * FibonacciHeap {
	var me *FibonacciHeap = &FibonacciHeap {}
	me.root = nil
	me.size = 0
	return me
}
// Simplest method of node insertion of Fibonacci min Heap
func(this *FibonacciHeap) insert(value int) {
	var node * HeapNode = getHeapNode(value)
	// Set initial node pointer
	// This is similar to circular doubly linked list
	node.left = node
	node.right = node
	if this.root == nil {
		// When insert first node
		this.root = node
	} else {
		this.root.left.right = node
		node.right = this.root
		node.left = this.root.left
		this.root.left = node
		if this.root.key > node.key {
			// Make new root
			this.root = node
		}
	}
	this.size++
}
// Display element of tree
func(this FibonacciHeap) dispaly() {
	if this.root == nil {
		fmt.Println("Empty Tree")
	} else {
		// Display root value
		fmt.Print("  ", this.root.key)
		var head * HeapNode = this.root.right
		// Display other element
		for (head != nil && head != this.root) {
			// Display node value
			fmt.Print("  ", head.key)
			// visit to right node
			head = head.right
		}
	}
}
func(this FibonacciHeap) totalNode() int {
	return this.size
}
func main() {
	var heap * FibonacciHeap = getFibonacciHeap()
	//Construct Tree
	heap.insert(5)
	heap.insert(7)
	heap.insert(4)
	heap.insert(3)
	heap.insert(9)
	heap.insert(14)
	heap.insert(2)
	heap.insert(1)
	heap.insert(6)
	heap.insert(11)
	// Display number of nodes
	fmt.Print("\n Total Nodes : ", heap.totalNode(), "\n")
	// Display node values
	heap.dispaly()
}

Output

 Total Nodes : 10
  1  2  3  4  5  7  9  14  6  11
<?php
/*
  Php program
  Simplest node insertion of Fibonacci Heap 
*/
class HeapNode
{
	public $left;
	public $right;
	public $key;
	public
	function __construct($value)
	{
		$this->key = $value;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class FibonacciHeap
{
	// This is use to store information of number of nodes in heap
	private $size;
	private $root;
	public
	function __construct()
	{
		$this->root = NULL;
		$this->size = 0;
	}
	// Simplest method of node insertion of Fibonacci min Heap
	public
	function insert($value)
	{
		$node = new HeapNode($value);
		// Set initial node pointer
		// This is similar to circular doubly linked list
		$node->left = $node;
		$node->right = $node;
		if ($this->root == NULL)
		{
			// When insert first node
			$this->root = $node;
		}
		else
		{
			$this->root->left->right = $node;
			$node->right = $this->root;
			$node->left = $this->root->left;
			$this->root->left = $node;
			if ($this->root->key > $node->key)
			{
				// Make new root
				$this->root = $node;
			}
		}
		$this->size++;
	}
	// Display element of tree
	public
	function dispaly()
	{
		if ($this->root == NULL)
		{
			echo("Empty Tree".
				"\n");
		}
		else
		{
			$head = $this->root;
			// Display other element
			while (true)
			{
				// Display node value
				echo("  ".$head->key);
				// visit to right node
				$head = $head->right;
				if ($head == null || $head === $this->root)
				{
					break;
				}
			}
		}
	}
	public
	function totalNode()
	{
		return $this->size;
	}
}

function main()
{
	$heap = new FibonacciHeap();
	//Construct Tree
	$heap->insert(5);
	$heap->insert(7);
	$heap->insert(4);
	$heap->insert(3);
	$heap->insert(9);
	$heap->insert(14);
	$heap->insert(2);
	$heap->insert(1);
	$heap->insert(6);
	$heap->insert(11);
	// Display number of nodes
	echo("\n Total Nodes : ".$heap->totalNode().
		"\n");
	// Display node values
	$heap->dispaly();
}
main();

Output

 Total Nodes : 10
  1  2  3  4  5  7  9  14  6  11
/*
  Node JS program
  Simplest node insertion of Fibonacci Heap 
*/
class HeapNode
{
	constructor(value)
	{
		this.key = value;
		this.left = null;
		this.right = null;
	}
}
class FibonacciHeap
{
	constructor()
	{
		this.root = null;
		this.size = 0;
	}
	// Simplest method of node insertion of Fibonacci min Heap
	insert(value)
	{
		var node = new HeapNode(value);
		// Set initial node pointer
		// This is similar to circular doubly linked list
		node.left = node;
		node.right = node;
		if (this.root == null)
		{
			// When insert first node
			this.root = node;
		}
		else
		{
			this.root.left.right = node;
			node.right = this.root;
			node.left = this.root.left;
			this.root.left = node;
			if (this.root.key > node.key)
			{
				// Make new root
				this.root = node;
			}
		}
		this.size++;
	}
	// Display element of tree
	dispaly()
	{
		if (this.root == null)
		{
			console.log("Empty Tree");
		}
		else
		{
			// Display root value
			process.stdout.write("  " + this.root.key);
			var head = this.root.right;
			// Display other element
			while (head != null && head != this.root)
			{
				// Display node value
				process.stdout.write("  " + head.key);
				// visit to right node
				head = head.right;
			}
		}
	}
	totalNode()
	{
		return this.size;
	}
}

function main()
{
	var heap = new FibonacciHeap();
	//Construct Tree
	heap.insert(5);
	heap.insert(7);
	heap.insert(4);
	heap.insert(3);
	heap.insert(9);
	heap.insert(14);
	heap.insert(2);
	heap.insert(1);
	heap.insert(6);
	heap.insert(11);
	// Display number of nodes
	process.stdout.write("\n Total Nodes : " + heap.totalNode() + "\n");
	// Display node values
	heap.dispaly();
}
main();

Output

 Total Nodes : 10
  1  2  3  4  5  7  9  14  6  11
#  Python 3 program
#  Simplest node insertion of Fibonacci Heap 
class HeapNode :
	def __init__(self, value) :
		self.key = value
		self.left = None
		self.right = None
	

class FibonacciHeap :
	#  This is use to store information of number of nodes in heap
	def __init__(self) :
		self.root = None
		self.size = 0
	
	#  Simplest method of node insertion of Fibonacci min Heap
	def insert(self, value) :
		node = HeapNode(value)
		#  Set initial node pointer
		#  This is similar to circular doubly linked list
		node.left = node
		node.right = node
		if (self.root == None) :
			#  When insert first node
			self.root = node
		else :
			self.root.left.right = node
			node.right = self.root
			node.left = self.root.left
			self.root.left = node
			if (self.root.key > node.key) :
				#  Make new root
				self.root = node
			
		
		self.size += 1
	
	#  Display element of tree
	def dispaly(self) :
		if (self.root == None) :
			print("Empty Tree")
		else :
			#  Display root value
			print("  ", self.root.key, end = "")
			head = self.root.right
			#  Display other element
			while (head != None and head != self.root) :
				#  Display node value
				print("  ", head.key, end = "")
				#  visit to right node
				head = head.right
			
		
	
	def totalNode(self) :
		return self.size
	

def main() :
	heap = FibonacciHeap()
	# Construct Tree
	heap.insert(5)
	heap.insert(7)
	heap.insert(4)
	heap.insert(3)
	heap.insert(9)
	heap.insert(14)
	heap.insert(2)
	heap.insert(1)
	heap.insert(6)
	heap.insert(11)
	#  Display number of nodes
	print("\n Total Nodes : ", heap.totalNode() )
	#  Display node values
	heap.dispaly()

if __name__ == "__main__": main()

Output

 Total Nodes :  10
   1   2   3   4   5   7   9   14   6   11
#  Ruby program
#  Simplest node insertion of Fibonacci Heap 
class HeapNode 
	# Define the accessor and reader of class HeapNode
	attr_reader :left, :right, :key
	attr_accessor :left, :right, :key
	def initialize(value) 
		self.key = value
		self.left = nil
		self.right = nil
	end

end

class FibonacciHeap 
	# Define the accessor and reader of class FibonacciHeap
	attr_reader :size, :root
	attr_accessor :size, :root
	#  This is use to store information of number of nodes in heap
	def initialize() 
		self.root = nil
		self.size = 0
	end

	#  Simplest method of node insertion of Fibonacci min Heap
	def insert(value) 
		node = HeapNode.new(value)
		#  Set initial node pointer
		#  This is similar to circular doubly linked list
		node.left = node
		node.right = node
		if (self.root == nil) 
			#  When insert first node
			self.root = node
		else
 
			self.root.left.right = node
			node.right = self.root
			node.left = self.root.left
			self.root.left = node
			if (self.root.key > node.key) 
				#  Make new root
				self.root = node
			end

		end

		self.size += 1
	end

	#  Display element of tree
	def dispaly() 
		if (self.root == nil) 
			print("Empty Tree", "\n")
		else
 
			#  Display root value
			print("  ", self.root.key)
			head = self.root.right
			#  Display other element
			while (head != nil && head != self.root) 
				#  Display node value
				print("  ", head.key)
				#  visit to right node
				head = head.right
			end

		end

	end

	def totalNode() 
		return self.size
	end

end

def main() 
	heap = FibonacciHeap.new()
	# Construct Tree
	heap.insert(5)
	heap.insert(7)
	heap.insert(4)
	heap.insert(3)
	heap.insert(9)
	heap.insert(14)
	heap.insert(2)
	heap.insert(1)
	heap.insert(6)
	heap.insert(11)
	#  Display number of nodes
	print("\n Total Nodes : ", heap.totalNode() ,"\n")
	#  Display node values
	heap.dispaly()
end

main()

Output

 Total Nodes : 10
  1  2  3  4  5  7  9  14  6  11
/*
  Scala program
  Simplest node insertion of Fibonacci Heap 
*/
class HeapNode(var left: HeapNode,
	var right: HeapNode,
		var key: Int)
{
	def this(value: Int)
	{
		this(null,null,value);
	}
}
class FibonacciHeap(
	// This is use to store information of number of nodes in heap
	var size: Int,
		var root: HeapNode)
{
	def this()
	{
		this(0,null);
	}
	// Simplest method of node insertion of Fibonacci min Heap
	def insert(value: Int): Unit = {
		var node: HeapNode = new HeapNode(value);
		// Set initial node pointer
		// This is similar to circular doubly linked list
		node.left = node;
		node.right = node;
		if (this.root == null)
		{
			// When insert first node
			this.root = node;
		}
		else
		{
			this.root.left.right = node;
			node.right = this.root;
			node.left = this.root.left;
			this.root.left = node;
			if (this.root.key > node.key)
			{
				// Make new root
				this.root = node;
			}
		}
		this.size += 1;
	}
	// Display element of tree
	def dispaly(): Unit = {
		if (this.root == null)
		{
			println("Empty Tree");
		}
		else
		{
			// Display root value
			print("  " + this.root.key);
			var head: HeapNode = this.root.right;
			// Display other element
			while (head != null && head != root)
			{
				// Display node value
				print("  " + head.key);
				// visit to right node
				head = head.right;
			}
		}
	}
	def totalNode(): Int = {
		return this.size;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var heap: FibonacciHeap = new FibonacciHeap();
		//Construct Tree
		heap.insert(5);
		heap.insert(7);
		heap.insert(4);
		heap.insert(3);
		heap.insert(9);
		heap.insert(14);
		heap.insert(2);
		heap.insert(1);
		heap.insert(6);
		heap.insert(11);
		// Display number of nodes
		print("\n Total Nodes : " + heap.totalNode() + "\n");
		// Display node values
		heap.dispaly();
	}
}

Output

 Total Nodes : 10
  1  2  3  4  5  7  9  14  6  11
/*
  Swift 4 program
  Simplest node insertion of Fibonacci Heap 
*/
class HeapNode
{
	var left: HeapNode? ;
	var right: HeapNode? ;
	var key: Int;
	init(_ value: Int)
	{
		self.key = value;
		self.left = nil;
		self.right = nil;
	}
}
class FibonacciHeap
{
	// This is use to store information of number of nodes in heap
	var size: Int;
	var root: HeapNode? ;
	init()
	{
		self.root = nil;
		self.size = 0;
	}
	// Simplest method of node insertion of Fibonacci min Heap
	func insert(_ value: Int)
	{
		let node: HeapNode = HeapNode(value);
		// Set initial node pointer
		// This is similar to circular doubly linked list
		node.left = node;
		node.right = node;
		if (self.root == nil)
		{
			// When insert first node
			self.root = node;
		}
		else
		{
			self.root!.left!.right = node;
			node.right = self.root;
			node.left = self.root!.left;
			self.root!.left = node;
			if (self.root!.key > node.key)
			{
				// Make new root
				self.root = node;
			}
		}
		self.size += 1;
	}
	// Display element of tree
	func dispaly()
	{
		if (self.root == nil)
		{
			print("Empty Tree");
		}
		else
		{
			// Display root value
			print("  ", self.root!.key, terminator: "");
			var head: HeapNode? = self.root!.right;
			// Display other element
			while (head  != nil && !(head === self.root))
			{
				// Display node value
				print("  ", head!.key, terminator: "");
				// visit to right node
				head = head!.right;
			}
		}
	}
	func totalNode() -> Int
	{
		return self.size;
	}
}
func main()
{
	let heap: FibonacciHeap = FibonacciHeap();
	//Construct Tree
	heap.insert(5);
	heap.insert(7);
	heap.insert(4);
	heap.insert(3);
	heap.insert(9);
	heap.insert(14);
	heap.insert(2);
	heap.insert(1);
	heap.insert(6);
	heap.insert(11);
	// Display number of nodes
	print("\n Total Nodes : ", heap.totalNode() );
	// Display node values
	heap.dispaly();
}
main();

Output

 Total Nodes :  10
   1   2   3   4   5   7   9   14   6   11
/*
  Kotlin program
  Simplest node insertion of Fibonacci Heap 
*/
class HeapNode
{
	var left: HeapNode ? ;
	var right: HeapNode ? ;
	var key: Int;
	constructor(value: Int)
	{
		this.key = value;
		this.left = null;
		this.right = null;
	}
}
class FibonacciHeap
{
	// This is use to store information of number of nodes in heap
	var size: Int;
	var root: HeapNode ? ;
	constructor()
	{
		this.root = null;
		this.size = 0;
	}
	// Simplest method of node insertion of Fibonacci min Heap
	fun insert(value: Int): Unit
	{
		val node: HeapNode = HeapNode(value);
		// Set initial node pointer
		// This is similar to circular doubly linked list
		node.left = node;
		node.right = node;
		if (this.root == null)
		{
			// When insert first node
			this.root = node;
		}
		else
		{
			this.root?.left?.right = node;
			node.right = this.root;
			node.left = this.root?.left;
			this.root?.left = node;
			if (this.root!!.key > node.key)
			{
				// Make new root
				this.root = node;
			}
		}
		this.size += 1;
	}
	// Display element of tree
	fun dispaly(): Unit
	{
		if (this.root == null)
		{
			println("Empty Tree");
		}
		else
		{
			// Display root value
			print("  " + this.root?.key);
			var head: HeapNode ? = this.root?.right;
			// Display other element
			while (head != null && head != this.root)
			{
				// Display node value
				print("  " + head.key);
				// visit to right node
				head = head.right;
			}
		}
	}
	fun totalNode(): Int
	{
		return this.size;
	}
}
fun main(args: Array < String > ): Unit
{
	val heap: FibonacciHeap = FibonacciHeap();
	//Construct Tree
	heap.insert(5);
	heap.insert(7);
	heap.insert(4);
	heap.insert(3);
	heap.insert(9);
	heap.insert(14);
	heap.insert(2);
	heap.insert(1);
	heap.insert(6);
	heap.insert(11);
	// Display number of nodes
	print("\n Total Nodes : " + heap.totalNode() + "\n");
	// Display node values
	heap.dispaly();
}

Output

 Total Nodes : 10
  1  2  3  4  5  7  9  14  6  11
Fibonacci Heap implementation

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment





Categories
Relative Post