Skip to main content

Binary Min Heap Tree Node Insertion

Here given code implementation process.

//C Program 
//Binary Min Heap Tree Node Insertion
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> //for bool

struct Node {
	int key;
	struct Node *left, *right;
};
struct MinHeap {

	struct Node *root;
	int size;

};

struct MinHeap *newHeap() {

	struct MinHeap *auxiliary = (struct MinHeap *) malloc(sizeof(struct MinHeap));

	if (auxiliary) {
		auxiliary->size = 0;
		auxiliary->root = NULL;
	} else {
		printf("Memory overflow\n");
	}
	return auxiliary;
}
struct Node *newNode(int key) {

	struct Node *auxiliary = (struct Node *) malloc(sizeof(struct Node));

	if (auxiliary) {
		auxiliary->key = key;
		auxiliary->left = auxiliary->right = NULL;
	} else {
		printf("Memory overflow\n");
	}
	return auxiliary;
}
//Get height of insert new node
int insertHeight(int size) {
	int i = 1;

	int sum = 0;

	while (size > sum + (1 << i)) {
		sum += (1 << i);
		i++;
	}
	return i;
}
void swapNode(struct Node *first, struct Node *second) {
	int key = first->key;

	first->key = second->key;
	second->key = key;
}
//Arrange node key
void arrangeNode(struct Node *root) {

	if (root->left != NULL && root->left->key < root->key) {
		swapNode(root, root->left);
	}
	if (root->right != NULL && root->right->key < root->key) {
		swapNode(root, root->right);
	}
}
bool addNode(struct Node *root, int height, int level, int key) {
	if (level >= height) {
		return false;
	}
	if (root != NULL) {

		if (level - 1 == height && root->left == NULL || root->right == NULL) {
			if (root->left == NULL) {
				root->left = newNode(key);
			} else {
				root->right = newNode(key);
			}

			arrangeNode(root);

			return true;
		}

		if (addNode(root->left, height, level + 1, key) || 
            addNode(root->right, height, level + 1, key)) {
			//Check effect of new inserted node
			arrangeNode(root);

			return true;
		}


	}
	return false;
}
void insert(struct MinHeap *heap, int key) {

	//Test case
	if (heap->root == NULL) {
		heap->root = newNode(key);
	} else if (heap->root->left == NULL) {
		heap->root->left = newNode(key);
		arrangeNode(heap->root);

	} else if (heap->root->right == NULL) {
		heap->root->right = newNode(key);
		arrangeNode(heap->root);
	} else {
		int height = insertHeight(heap->size);

		addNode(heap->root, height, 0, key);
	}
	heap->size++;
}
void preorder(struct Node *root) {
	if (root != NULL) {
		printf("  %d", root->key);
		preorder(root->left);

		preorder(root->right);
	}
}
int main() {
	struct MinHeap *heap = newHeap();

	//Construct  Min heap tree
	insert(heap, 5);
	insert(heap, 7);
	insert(heap, 4);
	insert(heap, 3);
	insert(heap, 9);
	insert(heap, 14);
	insert(heap, 2);
	insert(heap, 1);
	insert(heap, 6);
	insert(heap, 11);



	preorder(heap->root);
	/*After insert element*/

	/*
	           1
	         /    \
	        2      3 
	      /  \    /  \
	     4    9  14   5
	    / \   /
	   7   6  11
	*/

}

Output

  1  2  4  7  6  9  11  3  14  5
/*
  C++ program
  Binary Min Heap Tree Node Insertion
*/
//Tree node
#include<iostream>

using namespace std;
class Node {
	public:
	Node *left;
	Node *right;
	int key;
	Node(int value) {
		this->key = value;
		this->left = NULL;
		this->right = NULL;
	}
};
class MinHeap {
	public:

	//This is use to store information of number of nodes in Min heap
	int size;
	Node *root;
	MinHeap() {
		this->root = NULL;
		this->size = 0;
	}
	//Get height of insert new node
	int insertHeight() {
		int i = 1;
		int sum = 0;
		while (this->size > sum + (1 << i)) {
			sum += (1 << i);
			i++;
		}
		return i;
	}
	//interchange the two node value
	void swapNode(Node *first, Node *second) {
		int key = first->key;
		first->key = second->key;
		second->key = key;
	}
	//Arrange node key
	void arrangeNode(Node *head) {
		if (head->left != NULL && head->left->key < head->key) {
			this->swapNode(head, head->left);
		}
		if (head->right != NULL && head->right->key < head->key) {
			this->swapNode(head, head->right);
		}
	}
	bool addNode(Node *head, int height, int level, int value) {
		if (level >= height) {
			return false;
		}
		if (head != NULL) {
			if (level - 1 == height && head->left == NULL || head->right == NULL) {
				if (head->left == NULL) {
					head->left = new Node(value);
				} else {
					head->right = new Node(value);
				}
				this->arrangeNode(head);
				return true;
			}
			if (this->addNode(head->left, height, level + 1, value) || 
                this->addNode(head->right, height, level + 1, value)) {
				//Check effect of new inserted node
				this->arrangeNode(head);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	void insert(int value) {
		if (this->root == NULL) {
			this->root = new Node(value);
		} else
		if (this->root->left == NULL) {
			this->root->left = new Node(value);
			this->arrangeNode(this->root);
		} else if (this->root->right == NULL) {
			this->root->right = new Node(value);
			this->arrangeNode(this->root);
		} else {
			int height = this->insertHeight();
			this->addNode(this->root, height, 0, value);
		}
		this->size++;
	}
	void preorder(Node *head) {
		if (head != NULL) {
			cout << " " << head->key;
			this->preorder(head->left);
			this->preorder(head->right);
		}
	}
};
int main() {
	MinHeap obj =  MinHeap();
	//Construct first Min heap tree
	obj.insert(5);
	obj.insert(7);
	obj.insert(4);
	obj.insert(3);
	obj.insert(9);
	obj.insert(14);
	obj.insert(2);
	obj.insert(1);
	obj.insert(6);
	obj.insert(11);
	/*After insert element*/
	/*
			           1
			         /    \
			        2      3 
			      /  \    /  \
			     4    9  14   5
			    / \   /
			   7   6  11
			*/
	obj.preorder(obj.root);
	return 0;
}

Output

 1 2 4 7 6 9 11 3 14 5
/*
  Java program
  Binary Min Heap Tree Node Insertion
*/
//Tree node
class Node {

	public Node left;
	public Node right;

	public int key;

	public Node(int value) {
		key = value;
		left = null;
		right = null;
	}
}
public class MinHeap {



	//This is use to store information of number of nodes in Min heap
	public int size;

	public Node root;

	public MinHeap() {
		root = null;

		size = 0;
	}

	//Get height of insert new node
	public int insertHeight() {
		int i = 1;

		int sum = 0;

		while (this.size > sum + (1 << i)) {
			sum += (1 << i);
			i++;
		}
		return i;
	}
	//interchange the two node value
	public void swapNode(Node first, Node second) {
		int key = first.key;

		first.key = second.key;
		second.key = key;
	}
	//Arrange node key
	public void arrangeNode(Node head) {

		if (head.left != null && head.left.key < head.key) {
			swapNode(head, head.left);
		}
		if (head.right != null && head.right.key < head.key) {
			swapNode(head, head.right);
		}
	}
	public boolean addNode(Node head, int height, int level, int value) {
		if (level >= height) {
			return false;
		}
		if (head != null) {

			if (level - 1 == height && head.left == null ||
                head.right == null) {
				if (head.left == null) {
					head.left = new Node(value);
				} else {
					head.right = new Node(value);
				}

				arrangeNode(head);

				return true;
			}

			if (addNode(head.left, height, level + 1, value) ||
                addNode(head.right, height, level + 1, value)) {
				//Check effect of new inserted node
				arrangeNode(head);

				return true;
			}


		}
		return false;
	}
	//Handles the request to new inserting node
	public void insert(int value) {

		if (root == null) {
			root = new Node(value);
		} else if (root.left == null) {
			root.left = new Node(value);
			arrangeNode(root);

		} else if (root.right == null) {
			root.right = new Node(value);
			arrangeNode(root);
		} else {
			int height = insertHeight();

			addNode(root, height, 0, value);
		}
		this.size++;
	}

	public void preorder(Node head) {
		if (head != null) {
			System.out.print("  " + head.key);
			preorder(head.left);

			preorder(head.right);
		}
	}



	public static void main(String[] args) {

		MinHeap obj = new MinHeap();

		//Construct first Min heap tree
		obj.insert(5);
		obj.insert(7);
		obj.insert(4);
		obj.insert(3);
		obj.insert(9);
		obj.insert(14);
		obj.insert(2);
		obj.insert(1);
		obj.insert(6);
		obj.insert(11);

		/*After insert element*/

		/*
		           1
		         /    \
		        2      3 
		      /  \    /  \
		     4    9  14   5
		    / \   /
		   7   6  11
		*/
		obj.preorder(obj.root);
	}
}

Output

 1 2 4 7 6 9 11 3 14 5
/*
  C# program
  Binary Min Heap Tree Node Insertion
*/
//Tree node
using System;
public class Node {
	public Node left;
	public Node right;
	public int key;
	public Node(int value) {
		key = value;
		left = null;
		right = null;
	}
}
public class MinHeap {
	//This is use to store information of number of nodes in Min heap
	public int size;
	public Node root;
	public MinHeap() {
		root = null;
		size = 0;
	}
	//Get height of insert new node
	public int insertHeight() {
		int i = 1;
		int sum = 0;
		while (this.size > sum + (1 << i)) {
			sum += (1 << i);
			i++;
		}
		return i;
	}
	//interchange the two node value
	public void swapNode(Node first, Node second) {
		int key = first.key;
		first.key = second.key;
		second.key = key;
	}
	//Arrange node key
	public void arrangeNode(Node head) {
		if (head.left != null && head.left.key < head.key) {
			swapNode(head, head.left);
		}
		if (head.right != null && head.right.key < head.key) {
			swapNode(head, head.right);
		}
	}
	public Boolean addNode(Node head, int height, int level, int value) {
		if (level >= height) {
			return false;
		}
		if (head != null) {
			if (level - 1 == height && head.left == null || 
                head.right == null) {
				if (head.left == null) {
					head.left = new Node(value);
				} else {
					head.right = new Node(value);
				}
				arrangeNode(head);
				return true;
			}
			if (addNode(head.left, height, level + 1, value) || 
                addNode(head.right, height, level + 1, value)) {
				arrangeNode(head);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	public void insert(int value) {
		if (root == null) {
			root = new Node(value);
		} else
		if (root.left == null) {
			root.left = new Node(value);
			arrangeNode(root);
		} else
		if (root.right == null) {
			root.right = new Node(value);
			arrangeNode(root);
		} else {
			int height = insertHeight();
			addNode(root, height, 0, value);
		}
		this.size++;
	}
	public void preorder(Node head) {
		if (head != null) {
			Console.Write(" " + head.key);
			preorder(head.left);
			preorder(head.right);
		}
	}
	public static void Main(String[] args) {
		MinHeap obj = new MinHeap();
		obj.insert(5);
		obj.insert(7);
		obj.insert(4);
		obj.insert(3);
		obj.insert(9);
		obj.insert(14);
		obj.insert(2);
		obj.insert(1);
		obj.insert(6);
		obj.insert(11);
      	/*After insert element*/

		/*
		           1
		         /    \
		        2      3 
		      /  \    /  \
		     4    9  14   5
		    / \   /
		   7   6  11
		*/
		obj.preorder(obj.root);
	}
}

Output

 1 2 4 7 6 9 11 3 14 5
<?php
/*
  Php program
  Binary Min Heap Tree Node Insertion
*/
//Tree node
class Node {
	public $left;
	public $right;
	public $key;

	function __construct($value) {
		$this->key = $value;
		$this->left = null;
		$this->right = null;
	}
}
class MinHeap {
	//This is use to store information of number of nodes in Min heap

	public $size;
	public $root;

	function __construct() {
		$this->root = null;
		$this->size = 0;
	}
	//Get height of insert new node

	public 	function insertHeight() {
		$i = 1;
		$sum = 0;
		while ($this->size > $sum + (1 << $i)) {
			$sum += (1 << $i);
			$i++;
		}
		return $i;
	}
	//interchange the two node value
	public 	function swapNode($first, $second) {
		$key = $first->key;
		$first->key = $second->key;
		$second->key = $key;
	}
	//Arrange node key
	public 	function arrangeNode($head) {
		if ($head->left != null && $head->left->key < $head->key) {
			$this->swapNode($head, $head->left);
		}
		if ($head->right != null && $head->right->key < $head->key) {
			$this->swapNode($head, $head->right);
		}
	}
	public 	function addNode($head, $height, $level, $value) {
		if ($level >= $height) {
			return false;
		}
		if ($head != null) {
			if ($level - 1 == $height && $head->left == null || $head->right == null) {
				if ($head->left == null) {
					$head->left = new Node($value);
				} else {
					$head->right = new Node($value);
				}
				$this->arrangeNode($head);
				return true;
			}
			if ($this->addNode($head->left, $height, $level + 1, $value) || 
                $this->addNode($head->right, $height, $level + 1, $value)) {
				//Check effect of new inserted node
				$this->arrangeNode($head);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node

	public 	function insert($value) {
		if ($this->root == null) {
			$this->root = new Node($value);
		} else
		if ($this->root->left == null) {
			$this->root->left = new Node($value);
			$this->arrangeNode($this->root);
		} else
		if ($this->root->right == null) {
			$this->root->right = new Node($value);
			$this->arrangeNode($this->root);
		} else {
			$height = $this->insertHeight();
			$this->addNode($this->root, $height, 0, $value);
		}
		$this->size++;
	}
	public 	function preorder($head) {
		if ($head != null) {
			echo(" ". $head->key);
			$this->preorder($head->left);
			$this->preorder($head->right);
		}
	}
}

function main() {
	$obj = new MinHeap();
	//Construct first Min heap tree

	$obj->insert(5);
	$obj->insert(7);
	$obj->insert(4);
	$obj->insert(3);
	$obj->insert(9);
	$obj->insert(14);
	$obj->insert(2);
	$obj->insert(1);
	$obj->insert(6);
	$obj->insert(11);
	/*After insert element*/
	/*
			           1
			         /    \
			        2      3 
			      /  \    /  \
			     4    9  14   5
			    / \   /
			   7   6  11
			*/

	$obj->preorder($obj->root);

}
main();

Output

 1 2 4 7 6 9 11 3 14 5
/*
  Node Js program
  Binary Min Heap Tree Node Insertion
*/
//Tree node
class Node {
	constructor(value) {
		this.key = value;
		this.left = null;
		this.right = null;
	}
}
class MinHeap {
	constructor() {
		this.root = null;
		this.size = 0;
	}

	//Get height of insert new node
	insertHeight() {
		var i = 1;
		var sum = 0;
		while (this.size > sum + (1 << i)) {
			sum += (1 << i);
			i++;
		}

		return i;
	}

	//interchange the two node value
	swapNode(first, second) {
		var key = first.key;
		first.key = second.key;
		second.key = key;
	}

	//Arrange node key
	arrangeNode(head) {
		if (head.left != null && head.left.key < head.key) {
			this.swapNode(head, head.left);
		}

		if (head.right != null && head.right.key < head.key) {
			this.swapNode(head, head.right);
		}
	}
	addNode(head, height, level, value) {
		if (level >= height) {
			return false;
		}

		if (head != null) {
			if (level - 1 == height && head.left == null || head.right == null) {
				if (head.left == null) {
					head.left = new Node(value);
				} else {
					head.right = new Node(value);
				}
				this.arrangeNode(head);
				return true;
			}

			if (this.addNode(head.left, height, level + 1, value) || 
                this.addNode(head.right, height, level + 1, value)) {
				//Check effect of new inserted node
				this.arrangeNode(head);
				return true;
			}
		}

		return false;
	}

	//Handles the request to new inserting node
	insert(value) {
		if (this.root == null) {
			this.root = new Node(value);
		} else
		if (this.root.left == null) {
			this.root.left = new Node(value);
			this.arrangeNode(this.root);
		} else
		if (this.root.right == null) {
			this.root.right = new Node(value);
			this.arrangeNode(this.root);
		} else {
			var height = this.insertHeight();
			this.addNode(this.root, height, 0, value);
		}
		this.size++;
	}
	preorder(head) {
		if (head != null) {
			process.stdout.write(" " + head.key);
			this.preorder(head.left);
			this.preorder(head.right);
		}
	}
}

function main(args) {
	var obj = new MinHeap();
	//Construct first Min heap tree
	obj.insert(5);
	obj.insert(7);
	obj.insert(4);
	obj.insert(3);
	obj.insert(9);
	obj.insert(14);
	obj.insert(2);
	obj.insert(1);
	obj.insert(6);
	obj.insert(11);
	/*After insert element*/
	/*
			           1
			         /    \
			        2      3 
			      /  \    /  \
			     4    9  14   5
			    / \   /
			   7   6  11
			*/
	obj.preorder(obj.root);
}

main();

Output

 1 2 4 7 6 9 11 3 14 5
#   Python 3 program
#   Binary Min Heap Tree Node Insertion

# Tree node
class Node :
	
	def __init__(self, value) :
		self.key = value
		self.left = None
		self.right = None
	

class MinHeap :
	# This is use to store information of number of nodes in Min heap
	def __init__(self) :
		self.root = None
		self.size = 0
	
	# Get height of insert new node
	def insertHeight(self) :
		i = 1
		sum = 0
		while (self.size > sum + (1 << i)) :
			sum += (1 << i)
			i += 1
		
		return i
	
	# interchange the two node value
	def swapNode(self, first, second) :
		key = first.key
		first.key = second.key
		second.key = key
	
	# Arrange node key
	def arrangeNode(self, head) :
		if (head.left != None and head.left.key < head.key) :
			self.swapNode(head, head.left)
		
		if (head.right != None and head.right.key < head.key) :
			self.swapNode(head, head.right)
		
	
	def addNode(self, head, height, level, value) :
		if (level >= height) :
			return False
		
		if (head != None) :
			if (level - 1 == height and head.left == None or head.right == None) :
				if (head.left == None) :
					head.left = Node(value)
				else :
					head.right = Node(value)
				
				self.arrangeNode(head)
				return True
			
			if (self.addNode(head.left, height, level + 1, value) or 
                self.addNode(head.right, height, level + 1, value)) :
				# Check effect of new inserted node
				self.arrangeNode(head)
				return True
			
		
		return False
	
	# Handles the request to new inserting node
	def insert(self, value) :
		if (self.root == None) :
			self.root = Node(value)
		elif (self.root.left == None) :
			self.root.left = Node(value)
			self.arrangeNode(self.root)
		elif (self.root.right == None) :
			self.root.right = Node(value)
			self.arrangeNode(self.root)
		else :
			height = self.insertHeight()
			self.addNode(self.root, height, 0, value)
		
		self.size += 1
	
	def preorder(self, head) :
		if (head != None) :
			print(" ", head.key, end = "")
			self.preorder(head.left)
			self.preorder(head.right)
		
	

def main() :
	obj = MinHeap()
	# Construct first Min heap tree
	obj.insert(5)
	obj.insert(7)
	obj.insert(4)
	obj.insert(3)
	obj.insert(9)
	obj.insert(14)
	obj.insert(2)
	obj.insert(1)
	obj.insert(6)
	obj.insert(11)
	# After insert element
	 
	# 
	# 		           1
	# 		         /    \
	# 		        2      3 
	# 		      /  \    /  \
	# 		     4    9  14   5
	# 		    / \   /
	# 		   7   6  11
	# 		
	

	obj.preorder(obj.root)


if __name__ == "__main__":
	main()

Output

  1  2  4  7  6  9  11  3  14  5
#   Ruby program
#   Binary Min Heap Tree Node Insertion

 # Tree node
class Node 
	# Define the accessor and reader of class Node
    attr_reader :left, :right, :key
    attr_accessor :left, :right, :key
	def initialize(value) 
		@key = value
		@left = nil
		@right = nil
	end
end

class MinHeap 
	
	# Define the accessor and reader of class MinHeap
    # here size is use to store information of number of nodes in Min heap
    attr_reader :size, :root
    attr_accessor :size, :root
	def initialize() 
		@root = nil
		@size = 0
	end
	 # Get height of insert new node
	def insertHeight() 
		i = 1
		sum = 0
		while (self.size > sum + (1 << i)) 
			sum += (1 << i)
			i += 1
		end
		return i
	end
	 # interchange the two node value
	def swapNode(first, second) 
		key = first.key
		first.key = second.key
		second.key = key
	end
	 # Arrange node key
	def arrangeNode(head) 
		if (head.left != nil && head.left.key < head.key) 
			self.swapNode(head, head.left)
		end
		if (head.right != nil && head.right.key < head.key) 
			self.swapNode(head, head.right)
		end
	end
	def addNode(head, height, level, value) 
		if (level >= height) 
			return false
		end
		if (head != nil) 
			if (level - 1 == height && head.left == nil || head.right == nil) 
				if (head.left == nil) 
					head.left = Node.new(value)
				else 
					head.right = Node.new(value)
				end
				self.arrangeNode(head)
				return true
			end
			if (self.addNode(head.left, height, level + 1, value) || 
                self.addNode(head.right, height, level + 1, value)) 
				 # Check effect of new inserted node
				self.arrangeNode(head)
				return true
			end
		end
		return false
	end
	 # Handles the request to new inserting node
	def insert(value) 
		if (@root == nil) 
			@root = Node.new(value)
		elsif (@root.left == nil) 
			@root.left = Node.new(value)
			self.arrangeNode(@root)
		elsif (@root.right == nil) 
			@root.right = Node.new(value)
			self.arrangeNode(@root)
		else 
			height = self.insertHeight()
			self.addNode(@root, height, 0, value)
		end
		self.size += 1
	end
	def preorder(head) 
		if (head != nil) 
			print(" ", head.key)
			self.preorder(head.left)
			self.preorder(head.right)
		end
	end
end
def main() 
	obj = MinHeap.new()
	 # Construct first Min heap tree
	obj.insert(5)
	obj.insert(7)
	obj.insert(4)
	obj.insert(3)
	obj.insert(9)
	obj.insert(14)
	obj.insert(2)
	obj.insert(1)
	obj.insert(6)
	obj.insert(11)
	# After insert element
	 
	# 
	# 		           1
	# 		         /    \
	# 		        2      3 
	# 		      /  \    /  \
	# 		     4    9  14   5
	# 		    / \   /
	# 		   7   6  11
	# 		
	
	obj.preorder(obj.root)
end


main()

Output

 1 2 4 7 6 9 11 3 14 5
/*
  Scala program
  Binary Min Heap Tree Node Insertion
*/
//Tree node
class Node(var left: Node,
	var right: Node,
		var key: Int) {

	def this(key: Int) {
		this(null,null,key);
	}
} 
class MinHeap(var size: Int, 
              var root: Node) {
	def this() {
		this(0,null);
	}
	//Get height of insert new node
	def insertHeight(): Int = {
		var i: Int = 1;
		var sum: Int = 0;
		while (this.size > sum + (1 << i)) {
			sum += (1 << i);
			i += 1;
		}
		return i;
	}
	//interchange the two node value
	def swapNode(first: Node, second: Node): Unit = {
		val key: Int = first.key;
		first.key = second.key;
		second.key = key;
	}
	//Arrange node key
	def arrangeNode(head: Node): Unit = {
		if (head.left != null && head.left.key < head.key) {
			this.swapNode(head, head.left);
		}
		if (head.right != null && head.right.key < head.key) {
			this.swapNode(head, head.right);
		}
	}
	def addNode(head: Node, height: Int, level: Int, value: Int): Boolean = {
		if (level >= height) {
			return false;
		}
		if (head != null) {
			if (level - 1 == height && head.left == null || head.right == null) {
				if (head.left == null) {
					head.left = new Node(value);
				} else {
					head.right = new Node(value);
				}
				this.arrangeNode(head);

				return true;
			}
			if (this.addNode(head.left, height, level + 1, value) || 
                this.addNode(head.right, height, level + 1, value)) {
				//Check effect of new inserted node
				this.arrangeNode(head);

				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	def insert(value: Int): Unit = {
		if (this.root == null) {
			this.root = new Node(value);
		} else
		if (this.root.left == null) {
			this.root.left = new Node(value);
			this.arrangeNode(this.root);
		} else
		if (this.root.right == null) {
			this.root.right = new Node(value);
			this.arrangeNode(this.root);
		} else {
			val height: Int = this.insertHeight();
			this.addNode(this.root, height, 0, value);
		}
		this.size += 1;
	}
	def preorder(head: Node): Unit = {
		if (head != null) {
			print(" " + head.key);
			this.preorder(head.left);
			this.preorder(head.right);
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MinHeap = new MinHeap();

		//Construct first Min heap tree
		obj.insert(5);
		obj.insert(7);
		obj.insert(4);
		obj.insert(3);
		obj.insert(9);
		obj.insert(14);
		obj.insert(2);
		obj.insert(1);
		obj.insert(6);
		obj.insert(11);

		/*After insert element*/
		/*
				           1
				         /    \
				        2      3 
				      /  \    /  \
				     4    9  14   5
				    / \   /
				   7   6  11
				*/
		obj.preorder(obj.root);
	}
}

Output

 1 2 4 7 6 9 11 3 14 5
/*
  Swift program
  Binary Min Heap Tree Node Insertion
*/
//Tree node
class Node {
	var left: Node? ;
	var right: Node? ;
	var key: Int;
	init(_ value: Int) {
		key = value;
		left = nil;
		right = nil;
	}
}
class MinHeap {
	var size: Int;
	var root: Node? ;
	init() {
		root = nil;
		size = 0;
	}
	//Get height of insert new node
	func insertHeight() -> Int {
		var i = 1;
		var sum = 0;
		while (self.size > sum + (1 << i)) {
			sum += (1 << i);
			i += 1;
		}
		return i;
	}
	//interchange the two node value
	func swapNode(_ first: Node? , _ second : Node? ) {
		let key = first!.key;
		first!.key = second!.key;
		second!.key = key;
	}
	//Arrange node key
	func arrangeNode(_ head: Node? ) {
		if (head!.left != nil && head!.left!.key < head!.key) {
			self.swapNode(head, head!.left);
		}
		if (head!.right != nil && head!.right!.key < head!.key) {
			self.swapNode(head, head!.right);
		}
	}
	func addNode(_ head: Node? , _ height : Int, _ level: Int, _ value: Int) -> Bool {
		if (level >= height) {
			return false;
		}
		if (head != nil) {
			if (level - 1 == height && head!.left == nil || head!.right == nil) {
				if (head!.left == nil) {
					head!.left = Node(value);
				} else {
					head!.right = Node(value);
				}
				self.arrangeNode(head);
				return true;
			}
			if (self.addNode(head!.left, height, level + 1, value) || 
                self.addNode(head!.right, height, level + 1, value)) {
				//Check effect of new inserted node
				self.arrangeNode(head);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	func insert(_ value: Int) {
		if (root == nil) {
			root = Node(value);
		} else
		if (root!.left == nil) {
			root!.left = Node(value);
			self.arrangeNode(root);
		} else
		if (root!.right == nil) {
			root!.right = Node(value);
			self.arrangeNode(root);
		} else {
			let height = self.insertHeight();
			let _ = self.addNode(root, height, 0, value);
		}
		self.size += 1;
	}
	func preorder(_ head: Node? ) {
		if (head != nil) {
			print(" ", head!.key, terminator: "");
			self.preorder(head!.left);
			self.preorder(head!.right);
		}
	}
}
func main() {
	let obj = MinHeap();
	//Construct first Min heap tree
	obj.insert(5);
	obj.insert(7);
	obj.insert(4);
	obj.insert(3);
	obj.insert(9);
	obj.insert(14);
	obj.insert(2);
	obj.insert(1);
	obj.insert(6);
	obj.insert(11);
	/*After insert element*/
	/*
			           1
			         /    \
			        2      3 
			      /  \    /  \
			     4    9  14   5
			    / \   /
			   7   6  11
			*/
	obj.preorder(obj.root);
}
main();

Output

  1  2  4  7  6  9  11  3  14  5
Last updated on by Kalkicode




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