Binary Max Heap Tree Node Insertion
We are easily performed heap operations in array. But array are fixed size in most of programming language cannot change dynamically. In this post we are implement binary heap. This are size are not per define and that is stratified the properties of binary max heap.
1) The value of root node should be greater than or equal to child node.
2) Each leaf node should be exist in same level. And tree will be a complete tree.
Basically we can use in a two way to insert node in a binary max heap. By using a queue and recursion. This post is based on second approach. First see an example.
In this example given sequence is already in maxheap format. That is best case scenario. In other case when given sequence is not a form of max heap. In this situation we can need to change node values. For example.
Before view the solution think about how to implement this max heap using recursion in (O (n)) time. here n is the number of node in tree.
Note that in above both example we can add and remove note at any time. Here given code implementation process.
//C Program
//Binary Max Heap Tree Node Insertion
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> //for bool
struct Node
{
int key;
struct Node*left,*right;
};
struct MaxHeap
{
struct Node * root;
int size;
};
struct MaxHeap* newHeap()
{
struct MaxHeap*auxiliary = (struct MaxHeap*)malloc(sizeof(struct MaxHeap));
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 MaxHeap*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 MaxHeap *heap1=newHeap();
//Construct first Max heap tree
insert(heap1,5);
insert(heap1,7);
insert(heap1,4);
insert(heap1,3);
insert(heap1,9);
insert(heap1,14);
insert(heap1,2);
insert(heap1,1);
insert(heap1,6);
insert(heap1,11);
preorder(heap1->root);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
struct MaxHeap *heap2=newHeap();
//Construct second Min heap tree
for (int i=15;i> 0;i-- )
{
insert(heap2,i);
}
/*After insert element*/
/*
15
/ \
/ \
14 13
/ \ / \
12 11 10 9
/ \ / \ / \ / \
8 7 6 5 4 3 2 1
*/
printf("\n");
preorder(heap2->root);
return 0;
}
Output
14 11 6 1 3 7 5 9 4 2
15 14 12 8 7 11 6 5 13 10 4 3 9 2 1//C++ Program
//Binary Max Heap Tree Node Insertion
#include <iostream>
using namespace std;
class Node
{
public:
int key;
Node*left,*right;
Node(int key)
{
this->key=key;
left=right=NULL;
}
};
class MaxHeap
{
public:
Node * root;
int size;
MaxHeap()
{
root = NULL;
size = 0;
}
void preorder(Node *root);
bool addNode(Node *root, int height ,int level,int key);
void arrangeNode(Node *root);
int insertHeight();
void swapNode(Node *first,Node *second);
void insert(int key);
};
//Get height of insert new node
int MaxHeap:: insertHeight()
{
int i=1;
int sum=0;
while(this->size > sum+(1<<i) )
{
sum += (1<<i);
i++;
}
return i;
}
void MaxHeap:: swapNode(Node *first,Node *second)
{
int key = first->key;
first->key = second->key;
second->key = key;
}
//Arrange node key
void MaxHeap:: arrangeNode(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 MaxHeap:: addNode(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=new Node(key);
}
else
{
root->right=new Node(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 MaxHeap:: insert(int key)
{
//Test case
if(root==NULL)
{
root=new Node(key);
}
else if(root->left==NULL)
{
root->left = new Node(key);
arrangeNode(root);
}
else if(root->right==NULL)
{
root->right = new Node(key);
arrangeNode(root);
}
else
{
int height = insertHeight();
addNode(root,height, 0,key);
}
this->size++;
}
void MaxHeap:: preorder(Node *root)
{
if(root!=NULL)
{
cout<<" "<<root->key;
preorder(root->left);
preorder(root->right);
}
}
int main()
{
MaxHeap heap1;
//Construct first Max heap tree
heap1.insert(5);
heap1.insert(7);
heap1.insert(4);
heap1.insert(3);
heap1.insert(9);
heap1.insert(14);
heap1.insert(2);
heap1.insert(1);
heap1.insert(6);
heap1.insert(11);
heap1.preorder(heap1.root);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
MaxHeap heap2;
//Construct second Min heap tree
for (int i=15;i> 0;i-- )
{
heap2.insert(i);
}
/*After insert element*/
/*
15
/ \
/ \
14 13
/ \ / \
12 11 10 9
/ \ / \ / \ / \
8 7 6 5 4 3 2 1
*/
cout<<endl;
heap2.preorder(heap2.root);
return 0;
}
Output
14 11 6 1 3 7 5 9 4 2
15 14 12 8 7 11 6 5 13 10 4 3 9 2 1/*
Java program
Binary Max Heap Tree Node Insertion
*/
//Tree node
class Node {
//Left and right child
public Node left;
public Node right;
//Data value
public int key;
public Node(int key) {
this.key = key;
left = null;
right = null;
}
}
public class MaxHeap {
//This is use to store information of number of nodes in Max heap
public int size;
public Node root;
public MaxHeap() {
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;
}
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 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);
}
}
public boolean addNode(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 = new Node(key);
} else {
root.right = new Node(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;
}
//Handles the request to new inserting node
public void insert(int key) {
//Test case
if (root == null) {
root = new Node(key);
} else if (root.left == null) {
root.left = new Node(key);
arrangeNode(root);
} else if (root.right == null) {
root.right = new Node(key);
arrangeNode(root);
} else {
int height = insertHeight();
addNode(root, height, 0, key);
}
this.size++;
}
public void preorder(Node root) {
if (root != null) {
System.out.print(" " + root.key);
preorder(root.left);
preorder(root.right);
}
}
public static void main(String[] args) {
MaxHeap heap1 = new MaxHeap();
//Construct first Max heap tree
heap1.insert(5);
heap1.insert(7);
heap1.insert(4);
heap1.insert(3);
heap1.insert(9);
heap1.insert(14);
heap1.insert(2);
heap1.insert(1);
heap1.insert(6);
heap1.insert(11);
heap1.preorder(heap1.root);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
MaxHeap heap2 = new MaxHeap();
//Construct second Min heap tree
for (int i = 15; i > 0; i--) {
heap2.insert(i);
}
/*After insert element*/
/*
15
/ \
/ \
14 13
/ \ / \
12 11 10 9
/ \ / \ / \ / \
8 7 6 5 4 3 2 1
*/
System.out.println();
heap2.preorder(heap2.root);
}
}
Output
14 11 6 1 3 7 5 9 4 2
15 14 12 8 7 11 6 5 13 10 4 3 9 2 1
/*
C# program
Binary Max Heap Tree Node Insertion
*/
using System;
//Tree node
public class Node {
//Left and right child
public Node left;
public Node right;
//Data value
public int key;
public Node(int key) {
this.key = key;
left = null;
right = null;
}
}
public class MaxHeap {
//This is use to store information of number of nodes in Max heap
public int size;
public Node root;
public MaxHeap() {
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;
}
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 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);
}
}
public Boolean addNode(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 = new Node(key);
} else {
root.right = new Node(key);
}
arrangeNode(root);
return true;
}
if (addNode(root.left, height, level + 1, key) ||
addNode(root.right, height, level + 1, key)) {
arrangeNode(root);
return true;
}
}
return false;
}
//Handles the request to new inserting node
public void insert(int key) {
//Test case
if (root == null) {
root = new Node(key);
} else
if (root.left == null) {
root.left = new Node(key);
arrangeNode(root);
} else
if (root.right == null) {
root.right = new Node(key);
arrangeNode(root);
} else {
int height = insertHeight();
addNode(root, height, 0, key);
}
this.size++;
}
public void preorder(Node root) {
if (root != null) {
Console.Write(" " + root.key);
preorder(root.left);
preorder(root.right);
}
}
public static void Main(String[] args) {
MaxHeap heap1 = new MaxHeap();
heap1.insert(5);
heap1.insert(7);
heap1.insert(4);
heap1.insert(3);
heap1.insert(9);
heap1.insert(14);
heap1.insert(2);
heap1.insert(1);
heap1.insert(6);
heap1.insert(11);
heap1.preorder(heap1.root);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
MaxHeap heap2 = new MaxHeap();
//Construct second Min heap tree
for (int i = 15; i > 0; i--) {
heap2.insert(i);
}
Console.WriteLine();
heap2.preorder(heap2.root);
}
}
Output
14 11 6 1 3 7 5 9 4 2
15 14 12 8 7 11 6 5 13 10 4 3 9 2 1<?php
/*
Php program
Binary Max Heap Tree Node Insertion
*/
//Tree node
class Node {
//Left and right child
public $left;
public $right;
//Data value
public $key;
function __construct($key) {
$this->key = $key;
$this->left = null;
$this->right = null;
}
}
class MaxHeap {
//This is use to store information of number of nodes in Max 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;
}
public function swapNode($first, $second) {
$key = $first->key;
$first->key = $second->key;
$second->key = $key;
}
//Arrange node key
public function arrangeNode($root) {
if ($root->left != null && $root->left->key > $root->key) {
$this->swapNode($root, $root->left);
}
if ($root->right != null && $root->right->key > $root->key) {
$this->swapNode($root, $root->right);
}
}
public function addNode($root, $height, $level, $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 = new Node($key);
} else {
$root->right = new Node($key);
}
$this->arrangeNode($root);
return true;
}
if ($this->addNode($root->left, $height, $level + 1, $key) ||
$this->addNode($root->right, $height, $level + 1, $key)) {
//Check effect of new inserted node
$this->arrangeNode($root);
return true;
}
}
return false;
}
//Handles the request to new inserting node
public function insert($key) {
//Test case
if ($this->root == null) {
$this->root = new Node($key);
} else
if ($this->root->left == null) {
$this->root->left = new Node($key);
$this->arrangeNode($this->root);
} else
if ($this->root->right == null) {
$this->root->right = new Node($key);
$this->arrangeNode($this->root);
} else {
$height = $this->insertHeight();
$this->addNode($this->root, $height, 0, $key);
}
$this->size++;
}
public function preorder($root) {
if ($root != null) {
echo(" ". $root->key);
$this->preorder($root->left);
$this->preorder($root->right);
}
}
}
function main() {
$heap1 = new MaxHeap();
//Construct first Max heap tree
$heap1->insert(5);
$heap1->insert(7);
$heap1->insert(4);
$heap1->insert(3);
$heap1->insert(9);
$heap1->insert(14);
$heap1->insert(2);
$heap1->insert(1);
$heap1->insert(6);
$heap1->insert(11);
$heap1->preorder($heap1->root);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
$heap2 = new MaxHeap();
//Construct second Min heap tree
for ($i = 15; $i > 0; $i--) {
$heap2->insert($i);
}
/*After insert element*/
/*
15
/ \
/ \
14 13
/ \ / \
12 11 10 9
/ \ / \ / \ / \
8 7 6 5 4 3 2 1
*/
echo ("\n");
$heap2->preorder($heap2->root);
}
main();
Output
14 11 6 1 3 7 5 9 4 2
15 14 12 8 7 11 6 5 13 10 4 3 9 2 1/*
Node Js program
Binary Max Heap Tree Node Insertion
*/
//Tree node
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
class MaxHeap {
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;
}
swapNode(first, second) {
var temp = first.key;
first.key = second.key;
second.key = temp;
}
//Arrange node key
arrangeNode(root) {
if (root.left != null && root.left.key > root.key) {
this.swapNode(root, root.left);
}
if (root.right != null && root.right.key > root.key) {
this.swapNode(root, root.right);
}
}
addNode(root, height, level, 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 = new Node(key);
} else {
root.right = new Node(key);
}
this.arrangeNode(root);
return true;
}
if (this.addNode(root.left, height, level + 1, key) ||
this.addNode(root.right, height, level + 1, key)) {
//Check effect of new inserted node
this.arrangeNode(root);
return true;
}
}
return false;
}
//Handles the request to new inserting node
insert(key) {
//Test case
if (this.root == null) {
this.root = new Node(key);
} else
if (this.root.left == null) {
this.root.left = new Node(key);
this.arrangeNode(this.root);
} else
if (this.root.right == null) {
this.root.right = new Node(key);
this.arrangeNode(this.root);
} else {
var height = this.insertHeight();
this.addNode(this.root, height, 0, key);
}
this.size++;
}
preorder(root) {
if (root != null) {
process.stdout.write(" " + root.key);
this.preorder(root.left);
this.preorder(root.right);
}
}
}
function main(args) {
var heap1 = new MaxHeap();
//Construct first Max heap tree
heap1.insert(5);
heap1.insert(7);
heap1.insert(4);
heap1.insert(3);
heap1.insert(9);
heap1.insert(14);
heap1.insert(2);
heap1.insert(1);
heap1.insert(6);
heap1.insert(11);
heap1.preorder(heap1.root);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
var heap2 = new MaxHeap();
//Construct second Min heap tree
for (var i = 15; i > 0; i--) {
heap2.insert(i);
}
/*After insert element*/
/*
15
/ \
/ \
14 13
/ \ / \
12 11 10 9
/ \ / \ / \ / \
8 7 6 5 4 3 2 1
*/
process.stdout.write("\n");
heap2.preorder(heap2.root);
}
main();
Output
14 11 6 1 3 7 5 9 4 2
15 14 12 8 7 11 6 5 13 10 4 3 9 2 1# Python 3 program
# Binary Max Heap Tree Node Insertion
# Tree node
class Node :
def __init__(self, key) :
self.key = key
self.left = None
self.right = None
class MaxHeap :
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
def swapNode(self, first, second) :
temp = first.key
first.key = second.key
second.key = temp
# Arrange node key
def arrangeNode(self, root) :
if (root.left != None and root.left.key > root.key) :
self.swapNode(root, root.left)
if (root.right != None and root.right.key > root.key) :
self.swapNode(root, root.right)
def addNode(self, root, height, level, key) :
if (level >= height) :
return False
if (root != None) :
if (level - 1 == height and root.left == None or root.right == None) :
if (root.left == None) :
root.left = Node(key)
else :
root.right = Node(key)
self.arrangeNode(root)
return True
if (self.addNode(root.left, height, level + 1, key) or self.addNode(root.right, height, level + 1, key)) :
# Check effect of new inserted node
self.arrangeNode(root)
return True
return False
# Handles the request to new inserting node
def insert(self, key) :
# Test case
if (self.root == None) :
self.root = Node(key)
elif (self.root.left == None) :
self.root.left = Node(key)
self.arrangeNode(self.root)
elif (self.root.right == None) :
self.root.right = Node(key)
self.arrangeNode(self.root)
else :
height = self.insertHeight()
self.addNode(self.root, height, 0, key)
self.size += 1
def preorder(self, root) :
if (root != None) :
print(" ", root.key, end = "")
self.preorder(root.left)
self.preorder(root.right)
def main() :
heap1 = MaxHeap()
# Construct first Max heap tree
heap1.insert(5)
heap1.insert(7)
heap1.insert(4)
heap1.insert(3)
heap1.insert(9)
heap1.insert(14)
heap1.insert(2)
heap1.insert(1)
heap1.insert(6)
heap1.insert(11)
heap1.preorder(heap1.root)
# After insert element
#
# 14
# / \
# 11 9
# / \ / \
# 6 7 4 2
# / \ /
# 1 3 5
#
heap2 = MaxHeap()
i = 15
# Construct second Min heap tree
while (i > 0) :
heap2.insert(i)
i -= 1
print("\n", end = "")
heap2.preorder(heap2.root)
if __name__ == "__main__":
main()
Output
14 11 6 1 3 7 5 9 4 2
15 14 12 8 7 11 6 5 13 10 4 3 9 2 1# Ruby program
# Binary Max 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(key)
self.key = key
@left = nil
@right = nil
end
end
class MaxHeap
# Define the accessor and reader of class MaxHeap
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
def swapNode(first, second)
temp = first.key
first.key = second.key
second.key = temp
end
# Arrange node key
def arrangeNode(root)
if (root.left != nil && root.left.key > root.key)
self.swapNode(root, root.left)
end
if (root.right != nil && root.right.key > root.key)
self.swapNode(root, root.right)
end
end
def addNode(root, height, level, key)
if (level >= height)
return false
end
if (root != nil)
if (level - 1 == height && root.left == nil || root.right == nil)
if (root.left == nil)
root.left = Node.new(key)
else
root.right = Node.new(key)
end
self.arrangeNode(root)
return true
end
if (self.addNode(root.left, height, level + 1, key) ||
self.addNode(root.right, height, level + 1, key))
# Check effect of new inserted node
self.arrangeNode(root)
return true
end
end
return false
end
# Handles the request to new inserting node
def insert(key)
# Test case
if (@root == nil)
@root = Node.new(key)
elsif (@root.left == nil)
@root.left = Node.new(key)
self.arrangeNode(@root)
elsif (@root.right == nil)
@root.right = Node.new(key)
self.arrangeNode(@root)
else
height = self.insertHeight()
self.addNode(@root, height, 0, key)
end
self.size += 1
end
def preorder(root)
if (root != nil)
print(" ", root.key)
self.preorder(root.left)
self.preorder(root.right)
end
end
end
def main()
heap1 = MaxHeap.new()
# Construct first Max heap tree
heap1.insert(5)
heap1.insert(7)
heap1.insert(4)
heap1.insert(3)
heap1.insert(9)
heap1.insert(14)
heap1.insert(2)
heap1.insert(1)
heap1.insert(6)
heap1.insert(11)
heap1.preorder(heap1.root)
# After insert element
#
# 14
# / \
# 11 9
# / \ / \
# 6 7 4 2
# / \ /
# 1 3 5
#
heap2 = MaxHeap.new()
i = 15
# Construct second Min heap tree
while (i > 0)
heap2.insert(i)
i -= 1
end
# After insert element
#
# 15
# / \
# / \
# 14 13
# / \ / \
# 12 11 10 9
# / \ / \ / \ / \
# 8 7 6 5 4 3 2 1
#
print("\n")
heap2.preorder(heap2.root)
end
main()
Output
14 11 6 1 3 7 5 9 4 2
15 14 12 8 7 11 6 5 13 10 4 3 9 2 1/*
Scala program
Binary Max 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 MaxHeap(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;
}
def swapNode(first: Node, second: Node): Unit = {
val temp: Int = first.key;
first.key = second.key;
second.key = temp;
}
//Arrange node key
def arrangeNode(root: Node): Unit = {
if (root.left != null && root.left.key > root.key) {
this.swapNode(root, root.left);
}
if (root.right != null && root.right.key > root.key) {
this.swapNode(root, root.right);
}
}
def addNode(root: Node, height: Int, level: Int, key: Int): Boolean = {
if (level >= height) {
return false;
}
if (root != null) {
if (level - 1 == height && root.left == null || root.right == null) {
if (root.left == null) {
root.left = new Node(key);
} else {
root.right = new Node(key);
}
this.arrangeNode(root);
return true;
}
if (this.addNode(root.left, height, level + 1, key) ||
this.addNode(root.right, height, level + 1, key)) {
//Check effect of new inserted node
this.arrangeNode(root);
return true;
}
}
return false;
}
//Handles the request to new inserting node
def insert(key: Int): Unit = {
//Test case
if (this.root == null) {
this.root = new Node(key);
} else
if (this.root.left == null) {
this.root.left = new Node(key);
this.arrangeNode(this.root);
} else
if (this.root.right == null) {
this.root.right = new Node(key);
this.arrangeNode(this.root);
} else {
val height: Int = this.insertHeight();
this.addNode(this.root, height, 0, key);
}
this.size += 1;
}
def preorder(root: Node): Unit = {
if (root != null) {
print(" " + root.key);
this.preorder(root.left);
this.preorder(root.right);
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val heap1: MaxHeap = new MaxHeap();
//Construct first Max heap tree
heap1.insert(5);
heap1.insert(7);
heap1.insert(4);
heap1.insert(3);
heap1.insert(9);
heap1.insert(14);
heap1.insert(2);
heap1.insert(1);
heap1.insert(6);
heap1.insert(11);
heap1.preorder(heap1.root);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
var heap2: MaxHeap = new MaxHeap();
var i: Int = 15;
//Construct second Min heap tree
while (i > 0) {
heap2.insert(i);
i -= 1;
}
/*After insert element*/
/*
15
/ \
/ \
14 13
/ \ / \
12 11 10 9
/ \ / \ / \ / \
8 7 6 5 4 3 2 1
*/
print("\n");
heap2.preorder(heap2.root);
}
}
Output
14 11 6 1 3 7 5 9 4 2
15 14 12 8 7 11 6 5 13 10 4 3 9 2 1/*
Swift program
Binary Max Heap Tree Node Insertion
*/
//Tree node
class Node {
var left: Node? ;
var right: Node? ;
var key: Int;
init(_ key: Int) {
self.key = key;
left = nil;
right = nil;
}
}
class MaxHeap {
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;
}
func swapNode(_ first: Node? , _ second : Node? ) {
let temp = first!.key;
first!.key = second!.key;
second!.key = temp;
}
//Arrange node key
func arrangeNode(_ root: Node? ) {
if (root!.left != nil && root!.left!.key > root!.key) {
self.swapNode(root, root!.left);
}
if (root!.right != nil && root!.right!.key > root!.key) {
self.swapNode(root, root!.right);
}
}
func addNode(_ root: Node? , _ height : Int, _ level: Int, _ key: Int) -> Bool {
if (level >= height) {
return false;
}
if (root != nil) {
if (level - 1 == height && root!.left == nil || root!.right == nil) {
if (root!.left == nil) {
root!.left = Node(key);
} else {
root!.right = Node(key);
}
self.arrangeNode(root);
return true;
}
if (self.addNode(root!.left, height, level + 1, key) ||
self.addNode(root!.right, height, level + 1, key)) {
//Check effect of new inserted node
self.arrangeNode(root);
return true;
}
}
return false;
}
//Handles the request to new inserting node
func insert(_ key: Int) {
//Test case
if (root == nil) {
root = Node(key);
} else
if (root!.left == nil) {
root!.left = Node(key);
self.arrangeNode(root);
} else
if (root!.right == nil) {
root!.right = Node(key);
self.arrangeNode(root);
} else {
let height = self.insertHeight();
let _ = self.addNode(root, height, 0, key);
}
self.size += 1;
}
func preorder(_ root: Node? ) {
if (root != nil) {
print(" ", root!.key, terminator: "");
self.preorder(root!.left);
self.preorder(root!.right);
}
}
}
func main() {
let heap1 : MaxHeap? = MaxHeap();
//Construct first Max heap tree
heap1!.insert(5);
heap1!.insert(7);
heap1!.insert(4);
heap1!.insert(3);
heap1!.insert(9);
heap1!.insert(14);
heap1!.insert(2);
heap1!.insert(1);
heap1!.insert(6);
heap1!.insert(11);
heap1!.preorder(heap1!.root);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
let heap2 : MaxHeap? = MaxHeap();
var i = 15;
//Construct second Min heap tree
while (i > 0) {
heap2!.insert(i);
i -= 1;
}
print("\n", terminator: "");
heap2!.preorder(heap2!.root);
}
main();
Output
14 11 6 1 3 7 5 9 4 2
15 14 12 8 7 11 6 5 13 10 4 3 9 2 1
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