Print all nodes less than a given value in a Max Heap
In this post, we explore the problem of printing all nodes in a Max Heap that are less than a given value. A Max Heap is a binary tree structure where the value of each node is greater than or equal to the values of its children. We will discuss the approach to solving this problem, provide the necessary code, and analyze its time complexity.
Problem Statement and Description
Given a Max Heap and a target value k
, the task is to print all nodes in the Max Heap that have
values less than k
. In other words, we need to identify and print the nodes that are smaller than
the given value k
, while maintaining the Max Heap property.
Example
Consider the Max Heap shown below:
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
If the target value k
is 10, the nodes with values less than 10 are 1, 6, 3, 5, 7, 4, 9, and 2. The
expected output is 1 6 3 5 7 4 9 2
.
Approach
The main idea behind solving this problem is to traverse the Max Heap in an in-order manner while checking the values of nodes. Since in a Max Heap, parent nodes are always greater than their children, we can efficiently decide whether to traverse a subtree or not based on the value of the current node.
Pseudocode
function printNodesLessThanK(node, k)
if node is null
return
printNodesLessThanK(node.left, k)
if node.value < k
print node.value
printNodesLessThanK(node.right, k)
end function
main()
heap = createMaxHeap()
// Construct the Max Heap (insertions)
k = 10
printNodesLessThanK(heap.root, k)
end main
Algorithm Explanation
- Create a class
Node
representing a node in the Max Heap withleft
,right
, andkey
attributes. - Create a class
MaxHeap
with attributessize
androot
. Theroot
attribute points to the root of the Max Heap, andsize
keeps track of the number of nodes. - Implement the
printNodesLessThanK
function recursively:- Base case: If the current node is null, return.
- Recursively call
printNodesLessThanK
on the left subtree. - If the value of the current node is less than
k
, print the value. - Recursively call
printNodesLessThanK
on the right subtree.
- In the
main
function, create an instance ofMaxHeap
, perform insertions to construct the Max Heap, and define the value ofk
. - Call the
printNodesLessThanK
function with the root node of the Max Heap and valuek
.
Code Solution
/*
C++ program
Print all nodes less than a given value in a Max 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 MaxHeap {
public:
//This is use to store information of number of nodes in Max heap
int size;
Node *root;
MaxHeap() {
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;
}
void swapNode(Node *first, Node *second) {
int key = first->key;
first->key = second->key;
second->key = key;
}
//Arrange node key
void arrangeNode(Node *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);
}
}
bool 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);
}
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
void insert(int 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 {
int height = this->insertHeight();
this->addNode(this->root, height, 0, key);
}
this->size++;
}
void printNode(Node *root, int key) {
if (root != NULL) {
this->printNode(root->left, key);
if (root->key < key) {
//When element is less than of given key value
cout << " " << root->key;
}
this->printNode(root->right, key);
}
}
};
int main() {
MaxHeap heap = MaxHeap();
//Construct Min heap 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);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
int k = 10;
heap.printNode(heap.root, k);
return 0;
}
Output
1 6 3 5 7 4 9 2
/*
Java program
Print all nodes less than a given value in a Max 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 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 printNode(Node root, int key)
{
if (root != null) {
printNode(root.left, key);
if (root.key < key) {
//When element is less than of given key value
System.out.print(" " + root.key);
}
printNode(root.right, key);
}
}
public static void main(String[] args) {
MaxHeap heap = new MaxHeap();
//Construct Min heap 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);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
int k = 10;
heap.printNode(heap.root, k);
}
}
Output
1 6 3 5 7 4 9 2
/*
C# program
Print all nodes less than a given value in a Max Heap
*/
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 printNode(Node root, int key) {
if (root != null) {
printNode(root.left, key);
if (root.key < key) {
Console.Write(" " + root.key);
}
printNode(root.right, key);
}
}
public static void Main(String[] args) {
MaxHeap heap = new MaxHeap();
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);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
int k = 10;
heap.printNode(heap.root, k);
}
}
Output
1 6 3 5 7 4 9 2
<?php
/*
Php program
Print all nodes less than a given value in a Max 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 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 printNode($root, $key) {
if ($root != null) {
$this->printNode($root->left, $key);
if ($root->key < $key) {
//When element is less than of given key value
echo(" ". $root->key);
}
$this->printNode($root->right, $key);
}
}
}
function main() {
$heap = new MaxHeap();
//Construct Min heap 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);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
$k = 10;
$heap->printNode($heap->root, $k);
}
main();
Output
1 6 3 5 7 4 9 2
/*
Node Js program
Print all nodes less than a given value in a Max Heap
*/
//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 key = first.key;
first.key = second.key;
second.key = key;
}
//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++;
}
printNode(root, key) {
if (root != null) {
this.printNode(root.left, key);
if (root.key < key) {
//When element is less than of given key value
process.stdout.write(" " + root.key);
}
this.printNode(root.right, key);
}
}
}
function main(args) {
var heap = new MaxHeap();
//Construct Min heap 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);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
var k = 10;
heap.printNode(heap.root, k);
}
main();
Output
1 6 3 5 7 4 9 2
# Python 3 program
# Print all nodes less than a given value in a Max Heap
# 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) :
key = first.key
first.key = second.key
second.key = key
# 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 printNode(self, root, key) :
if (root != None) :
self.printNode(root.left, key)
if (root.key < key) :
print(" ", root.key, end = "")
self.printNode(root.right, key)
def main() :
heap = MaxHeap() # Construct Min heap 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)
#
# 14
# / \
# 11 9
# / \ / \
# 6 7 4 2
# / \ /
# 1 3 5
#
#After insert element
#
# 14
# / \
# 11 9
# / \ / \
# 6 7 4 2
# / \ /
# 1 3 5
#
k = 10
heap.printNode(heap.root, k)
if __name__ == "__main__":
main()
Output
1 6 3 5 7 4 9 2
# Ruby program
# Print all nodes less than a given value in a Max 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 MaxHeap
# Define the accessor and reader of class MaxHeap
# size is use to store information of number of nodes in Max 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
def swapNode(first, second)
key = first.key
first.key = second.key
second.key = key
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 printNode(root, key)
if (root != nil)
self.printNode(root.left, key)
if (root.key < key)
# When element is less than of given key value
print(" ", root.key)
end
self.printNode(root.right, key)
end
end
end
def main()
heap = MaxHeap.new()
# Construct Min heap 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)
#After insert element
#
# 14
# / \
# 11 9
# / \ / \
# 6 7 4 2
# / \ /
# 1 3 5
#
k = 10
heap.printNode(heap.root, k)
end
main()
Output
1 6 3 5 7 4 9 2
/*
Scala program
Print all nodes less than a given value in a Max Heap
*/
//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 = {
var key: Int = first.key;
first.key = second.key;
second.key = key;
}
//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 printNode(root: Node, key: Int): Unit = {
if (root != null) {
this.printNode(root.left, key);
if (root.key < key) {
//When element is less than of given key value
print(" " + root.key);
}
this.printNode(root.right, key);
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val heap: MaxHeap = new MaxHeap();
//Construct Min heap 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);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
var k: Int = 10;
heap.printNode(heap.root, k);
}
}
Output
1 6 3 5 7 4 9 2
/*
Swift program
Print all nodes less than a given value in a Max Heap
*/
//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 key = first!.key;
first!.key = second!.key;
second!.key = key;
}
//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 printNode(_ root: Node? , _ key : Int) {
if (root != nil) {
self.printNode(root!.left, key);
if (root!.key < key) {
print(" ", root!.key, terminator: "");
}
self.printNode(root!.right, key);
}
}
}
func main() {
let heap = MaxHeap();
//Construct Min heap 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);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
let k = 10;
heap.printNode(heap.root, k);
}
main();
Output
1 6 3 5 7 4 9 2
Time Complexity
The time complexity of this algorithm is O(n), where n is the number of nodes in the Max Heap. This is because each node is visited exactly once during the traversal, and the operations performed at each node take constant time. Therefore, the time complexity is linear with respect to the number of nodes in the Max Heap.
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