Print all nodes less than a given value in a Min Heap
Here given code implementation process.
/*
C++ program
Print all nodes less than a given value in a Min Heap
*/
//Tree node
#include<iostream>
using namespace std;
class Node {
public:
//Left and right child
Node *left;
Node *right;
//Data value
int key;
Node(int key) {
this->key = key;
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 insert_height() {
int i = 1;
int sum = 0;
while (this->size > sum + (1 << i)) {
sum += (1 << i);
i++;
}
return i;
}
void swap_node(Node *first, Node *second) {
int key = first->key;
first->key = second->key;
second->key = key;
}
//Arrange node key
void arrange_node(Node *root) {
if (root->left != NULL && root->left->key < root->key) {
this->swap_node(root, root->left);
}
if (root->right != NULL && root->right->key < root->key) {
this->swap_node(root, root->right);
}
}
bool add_node(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);
}
this->arrange_node(root);
return true;
}
if (this->add_node(root->left, height, level + 1, key) ||
this->add_node(root->right, height, level + 1, key)) {
//Check effect of new inserted node
this->arrange_node(root);
return true;
}
}
return false;
}
//Handles the request to new inserting node
void insert(int key) {
if (this->root == NULL) {
this->root = new Node(key);
} else
if (this->root->left == NULL) {
this->root->left = new Node(key);
this->arrange_node(this->root);
} else
if (this->root->right == NULL) {
this->root->right = new Node(key);
this->arrange_node(this->root);
} else {
int height = this->insert_height();
this->add_node(this->root, height, 0, key);
}
this->size++;
}
void print_node(Node *root, int key) {
if (root != NULL) {
this->print_node(root->left, key);
if (root->key < key) {
cout << " " << root->key;
}
this->print_node(root->right, key);
}
}
};
int main() {
MinHeap heap = MinHeap();
//Construct first Min heap tree
heap.insert(5);
heap.insert(7);
heap.insert(4);
heap.insert(3);
heap.insert(8);
heap.insert(14);
heap.insert(2);
heap.insert(1);
heap.insert(6);
heap.insert(11);
heap.insert(9);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 8 14 5
/ \ /\
7 6 11 9
*/
int k = 10;
heap.print_node(heap.root, k);
return 0;
}
Output
7 4 6 2 8 9 1 3 5
/*
Java program
Print all nodes less than a given value in a Min Heap
*/
//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 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 insert_height()
{
int i=1;
int sum=0;
while(this.size > sum+(1<<i) )
{
sum += (1<<i);
i++;
}
return i;
}
public void swap_node(Node first,Node second)
{
int key = first.key;
first.key = second.key;
second.key = key;
}
//Arrange node key
public void arrange_node(Node root)
{
if(root.left!=null && root.left.key < root.key)
{
swap_node(root,root.left);
}
if(root.right!=null && root.right.key < root.key)
{
swap_node(root,root.right);
}
}
public boolean add_node(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);
}
arrange_node(root);
return true;
}
if(add_node(root.left, height, level+1,key) || add_node(root.right, height,level+1,key))
{
//Check effect of new inserted node
arrange_node(root);
return true;
}
}
return false;
}
//Handles the request to new inserting node
public void insert(int key)
{
if(root==null)
{
root=new Node(key);
}
else if(root.left==null)
{
root.left = new Node(key);
arrange_node(root);
}
else if(root.right==null)
{
root.right = new Node(key);
arrange_node(root);
}
else
{
int height = insert_height();
add_node(root,height, 0,key);
}
this.size++;
}
public void print_node(Node root,int key)
{
if(root!=null)
{
print_node(root.left,key);
if(root.key < key)
{
System.out.print(" "+root.key);
}
print_node(root.right,key);
}
}
public static void main(String[] args)
{
MinHeap heap= new MinHeap();
//Construct first Min heap tree
heap.insert(5);
heap.insert(7);
heap.insert(4);
heap.insert(3);
heap.insert(8);
heap.insert(14);
heap.insert(2);
heap.insert(1);
heap.insert(6);
heap.insert(11);
heap.insert(9);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 8 14 5
/ \ /\
7 6 11 9
*/
int k = 10;
heap.print_node(heap.root,k);
}
}
Output
7 4 6 2 8 9 1 3 5
/*
C# program
Print all nodes less than a given value in a Min Heap
*/
//Tree node
using System;
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 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 insert_height() {
int i = 1;
int sum = 0;
while (this.size > sum + (1 << i)) {
sum += (1 << i);
i++;
}
return i;
}
public void swap_node(Node first, Node second) {
int key = first.key;
first.key = second.key;
second.key = key;
}
//Arrange node key
public void arrange_node(Node root) {
if (root.left != null && root.left.key < root.key) {
swap_node(root, root.left);
}
if (root.right != null && root.right.key < root.key) {
swap_node(root, root.right);
}
}
public Boolean add_node(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);
}
arrange_node(root);
return true;
}
if (add_node(root.left, height, level + 1, key) || add_node(root.right, height, level + 1, key)) {
arrange_node(root);
return true;
}
}
return false;
}
//Handles the request to new inserting node
public void insert(int key) {
if (root == null) {
root = new Node(key);
} else
if (root.left == null) {
root.left = new Node(key);
arrange_node(root);
} else
if (root.right == null) {
root.right = new Node(key);
arrange_node(root);
} else {
int height = insert_height();
add_node(root, height, 0, key);
}
this.size++;
}
public void print_node(Node root, int key) {
if (root != null) {
print_node(root.left, key);
if (root.key < key) {
Console.Write(" " + root.key);
}
print_node(root.right, key);
}
}
public static void Main(String[] args) {
MinHeap heap = new MinHeap();
heap.insert(5);
heap.insert(7);
heap.insert(4);
heap.insert(3);
heap.insert(8);
heap.insert(14);
heap.insert(2);
heap.insert(1);
heap.insert(6);
heap.insert(11);
heap.insert(9);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 8 14 5
/ \ /\
7 6 11 9
*/
int k = 10;
heap.print_node(heap.root, k);
}
}
Output
7 4 6 2 8 9 1 3 5
<?php
/*
Php program
Print all nodes less than a given value in a Min Heap
*/
//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 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 insert_height() {
$i = 1;
$sum = 0;
while ($this->size > $sum + (1 << $i)) {
$sum += (1 << $i);
$i++;
}
return $i;
}
public function swap_node($first, $second) {
$data = $first->key;
$first->key = $second->key;
$second->key = $data;
}
//Arrange node key
public function arrange_node($root) {
if ($root->left != null && $root->left->key < $root->key) {
$this->swap_node($root, $root->left);
}
if ($root->right != null && $root->right->key < $root->key) {
$this->swap_node($root, $root->right);
}
}
public function add_node($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->arrange_node($root);
return true;
}
if ($this->add_node($root->left, $height, $level + 1, $key) || $this->add_node($root->right, $height, $level + 1, $key)) {
//Check effect of new inserted node
$this->arrange_node($root);
return true;
}
}
return false;
}
//Handles the request to new inserting node
public function insert($key) {
if ($this->root == null) {
$this->root = new Node($key);
} else
if ($this->root->left == null) {
$this->root->left = new Node($key);
$this->arrange_node($this->root);
} else
if ($this->root->right == null) {
$this->root->right = new Node($key);
$this->arrange_node($this->root);
} else {
$height = $this->insert_height();
$this->add_node($this->root, $height, 0, $key);
}
$this->size++;
}
public function print_node($root, $key) {
if ($root != null) {
$this->print_node($root->left, $key);
if ($root->key < $key) {
echo(" ". $root->key);
}
$this->print_node($root->right, $key);
}
}
}
function main() {
$heap = new MinHeap();
//Construct first Min heap tree
$heap->insert(5);
$heap->insert(7);
$heap->insert(4);
$heap->insert(3);
$heap->insert(8);
$heap->insert(14);
$heap->insert(2);
$heap->insert(1);
$heap->insert(6);
$heap->insert(11);
$heap->insert(9);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 8 14 5
/ \ /\
7 6 11 9
*/
$k = 10;
$heap->print_node($heap->root, $k);
}
main();
Output
7 4 6 2 8 9 1 3 5
/*
Node Js program
Print all nodes less than a given value in a Min Heap
*/
//Tree node
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
class MinHeap {
constructor() {
this.root = null;
this.size = 0;
}
//Get height of insert new node
insert_height() {
var i = 1;
var sum = 0;
while (this.size > sum + (1 << i)) {
sum += (1 << i);
i++;
}
return i;
}
swap_node(first, second) {
var data = first.key;
first.key = second.key;
second.key = data;
}
//Arrange node key
arrange_node(root) {
if (root.left != null && root.left.key < root.key) {
this.swap_node(root, root.left);
}
if (root.right != null && root.right.key < root.key) {
this.swap_node(root, root.right);
}
}
add_node(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.arrange_node(root);
return true;
}
if (this.add_node(root.left, height, level + 1, key) || this.add_node(root.right, height, level + 1, key)) {
//Check effect of new inserted node
this.arrange_node(root);
return true;
}
}
return false;
}
//Handles the request to new inserting node
insert(key) {
if (this.root == null) {
this.root = new Node(key);
} else
if (this.root.left == null) {
this.root.left = new Node(key);
this.arrange_node(this.root);
} else
if (this.root.right == null) {
this.root.right = new Node(key);
this.arrange_node(this.root);
} else {
var height = this.insert_height();
this.add_node(this.root, height, 0, key);
}
this.size++;
}
print_node(root, key) {
if (root != null) {
this.print_node(root.left, key);
if (root.key < key) {
process.stdout.write(" " + root.key);
}
this.print_node(root.right, key);
}
}
}
function main(args) {
var heap = new MinHeap();
//Construct first Min heap tree
heap.insert(5);
heap.insert(7);
heap.insert(4);
heap.insert(3);
heap.insert(8);
heap.insert(14);
heap.insert(2);
heap.insert(1);
heap.insert(6);
heap.insert(11);
heap.insert(9);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 8 14 5
/ \ /\
7 6 11 9
*/
var k = 10;
heap.print_node(heap.root, k);
}
main();
Output
7 4 6 2 8 9 1 3 5
# Python 3 program
# Print all nodes less than a given value in a Min Heap
# Tree node
class Node :
def __init__(self, key) :
self.key = key
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 insert_height(self) :
i = 1
sum = 0
while (self.size > sum + (1 << i)) :
sum += (1 << i)
i += 1
return i
def swap_node(self, first, second) :
data = first.key
first.key = second.key
second.key = data
# Arrange node key
def arrange_node(self, root) :
if (root.left != None and root.left.key < root.key) :
self.swap_node(root, root.left)
if (root.right != None and root.right.key < root.key) :
self.swap_node(root, root.right)
def add_node(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.arrange_node(root)
return True
if (self.add_node(root.left, height, level + 1, key) or self.add_node(root.right, height, level + 1, key)) :
# Check effect of new inserted node
self.arrange_node(root)
return True
return False
# Handles the request to new inserting node
def insert(self, key) :
if (self.root == None) :
self.root = Node(key)
elif (self.root.left == None) :
self.root.left = Node(key)
self.arrange_node(self.root)
elif (self.root.right == None) :
self.root.right = Node(key)
self.arrange_node(self.root)
else :
height = self.insert_height()
self.add_node(self.root, height, 0, key)
self.size += 1
def print_node(self, root, key) :
if (root != None) :
self.print_node(root.left, key)
if (root.key < key) :
print(" ", root.key, end = "")
self.print_node(root.right, key)
def main() :
heap = MinHeap()
# Construct first Min heap tree
heap.insert(5)
heap.insert(7)
heap.insert(4)
heap.insert(3)
heap.insert(8)
heap.insert(14)
heap.insert(2)
heap.insert(1)
heap.insert(6)
heap.insert(11)
heap.insert(9)
#After insert element
#
# 1
# / \
# 2 3
# / \ / \
# 4 8 14 5
# / \ /\
# 7 6 11 9
#
k = 10
heap.print_node(heap.root, k)
if __name__ == "__main__":
main()
Output
7 4 6 2 8 9 1 3 5
# Ruby program
# Print all nodes less than a given value in a Min Heap
# 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 MinHeap
# Define the accessor and reader of class MinHeap
attr_reader :size, :root
attr_accessor :size, :root
def initialize()
@root = nil
@size = 0
end
# Get height of insert new node
def insert_height()
i = 1
sum = 0
while (self.size > sum + (1 << i))
sum += (1 << i)
i += 1
end
return i
end
def swap_node(first, second)
data = first.key
first.key = second.key
second.key = data
end
# Arrange node key
def arrange_node(root)
if (root.left != nil && root.left.key < root.key)
self.swap_node(root, root.left)
end
if (root.right != nil && root.right.key < root.key)
self.swap_node(root, root.right)
end
end
def add_node(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.arrange_node(root)
return true
end
if (self.add_node(root.left, height, level + 1, key) || self.add_node(root.right, height, level + 1, key))
# Check effect of new inserted node
self.arrange_node(root)
return true
end
end
return false
end
# Handles the request to new inserting node
def insert(key)
if (@root == nil)
@root = Node.new(key)
elsif (@root.left == nil)
@root.left = Node.new(key)
self.arrange_node(@root)
elsif (@root.right == nil)
@root.right = Node.new(key)
self.arrange_node(@root)
else
height = self.insert_height()
self.add_node(@root, height, 0, key)
end
self.size += 1
end
def print_node(root, key)
if (root != nil)
self.print_node(root.left, key)
if (root.key < key)
print(" ", root.key)
end
self.print_node(root.right, key)
end
end
end
def main()
heap = MinHeap.new()
# Construct first Min heap tree
heap.insert(5)
heap.insert(7)
heap.insert(4)
heap.insert(3)
heap.insert(8)
heap.insert(14)
heap.insert(2)
heap.insert(1)
heap.insert(6)
heap.insert(11)
heap.insert(9)
#After insert element
#
# 1
# / \
# 2 3
# / \ / \
# 4 8 14 5
# / \ /\
# 7 6 11 9
#
k = 10
heap.print_node(heap.root, k)
end
main()
Output
7 4 6 2 8 9 1 3 5
/*
Scala program
Print all nodes less than a given value in a Min Heap
*/
//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 insert_height(): Int = {
var i: Int = 1;
var sum: Int = 0;
while (this.size > sum + (1 << i)) {
sum += (1 << i);
i += 1;
}
return i;
}
def swap_node(first: Node, second: Node): Unit = {
val data: Int = first.key;
first.key = second.key;
second.key = data;
}
//Arrange node key
def arrange_node(root: Node): Unit = {
if (root.left != null && root.left.key < root.key) {
this.swap_node(root, root.left);
}
if (root.right != null && root.right.key < root.key) {
this.swap_node(root, root.right);
}
}
def add_node(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.arrange_node(root);
return true;
}
if (this.add_node(root.left, height, level + 1, key) || this.add_node(root.right, height, level + 1, key)) {
//Check effect of new inserted node
this.arrange_node(root);
return true;
}
}
return false;
}
//Handles the request to new inserting node
def insert(key: Int): Unit = {
if (this.root == null) {
this.root = new Node(key);
} else
if (this.root.left == null) {
this.root.left = new Node(key);
this.arrange_node(this.root);
} else
if (this.root.right == null) {
this.root.right = new Node(key);
this.arrange_node(this.root);
} else {
val height: Int = this.insert_height();
this.add_node(this.root, height, 0, key);
}
this.size += 1;
}
def print_node(root: Node, key: Int): Unit = {
if (root != null) {
this.print_node(root.left, key);
if (root.key < key) {
print(" " + root.key);
}
this.print_node(root.right, key);
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val heap: MinHeap = new MinHeap();
//Construct first Min heap tree
heap.insert(5);
heap.insert(7);
heap.insert(4);
heap.insert(3);
heap.insert(8);
heap.insert(14);
heap.insert(2);
heap.insert(1);
heap.insert(6);
heap.insert(11);
heap.insert(9);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 8 14 5
/ \ /\
7 6 11 9
*/
var k: Int = 10;
heap.print_node(heap.root, k);
}
}
Output
7 4 6 2 8 9 1 3 5
/*
Swift program
Print all nodes less than a given value in a Min Heap
*/
//Tree node
class Node {
//Left and right child
var left : Node?;
var right : Node?;
//Data value
var key : Int;
init(_ key: Int) {
self.key = key;
self.left = nil;
self.right = nil;
}
}
class MinHeap {
//This is use to store information of number of nodes in Min heap
var size : Int;
var root : Node?;
init() {
self.root = nil;
self.size = 0;
}
//Get height of insert new node
func insert_height() -> Int {
var i = 1;
var sum = 0;
while (self.size > sum + (1 << i)) {
sum += (1 << i);
i += 1;
}
return i;
}
func swap_node(_ first: Node?, _ second: Node?) {
let data = first!.key;
first!.key = second!.key;
second!.key = data;
}
//Arrange node key
func arrange_node(_ root: Node?) {
if (root!.left != nil && root!.left!.key < root!.key) {
self.swap_node(root, root!.left);
}
if (root!.right != nil && root!.right!.key < root!.key) {
self.swap_node(root, root!.right);
}
}
func add_node(_ 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.arrange_node(root);
return true;
}
if (self.add_node(root!.left, height, level + 1, key) || self.add_node(root!.right, height, level + 1, key)) {
//Check effect of new inserted node
self.arrange_node(root);
return true;
}
}
return false;
}
//Handles the request to new inserting node
func insert(_ key: Int) {
if (self.root == nil) {
self.root = Node(key);
} else
if (self.root!.left == nil) {
self.root!.left = Node(key);
self.arrange_node(self.root);
} else
if (self.root!.right == nil) {
self.root!.right = Node(key);
self.arrange_node(self.root);
} else {
let height = self.insert_height();
let _ = self.add_node(self.root, height, 0, key);
}
self.size += 1;
}
func print_node(_ root: Node?, _ key: Int) {
if (root != nil) {
self.print_node(root!.left, key);
if (root!.key < key) {
print(" ", root!.key, terminator: "");
}
self.print_node(root!.right, key);
}
}
}
func main() {
let heap = MinHeap();
//Construct first Min heap tree
heap.insert(5);
heap.insert(7);
heap.insert(4);
heap.insert(3);
heap.insert(8);
heap.insert(14);
heap.insert(2);
heap.insert(1);
heap.insert(6);
heap.insert(11);
heap.insert(9);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 8 14 5
/ \ /\
7 6 11 9
*/
let k = 10;
heap.print_node(heap.root, k);
}
main();
Output
7 4 6 2 8 9 1 3 5
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