Posted on by Kalkicode
Code Heap

Print all nodes less than a given value in a Min Heap

In this problem of printing all nodes in a Min Heap that have values less than a given threshold. A Min Heap is a binary tree structure where the value of each node is smaller than or equal to the values of its children. We will delve into the approach to solving this problem, present the code implementation, analyze its time complexity, and provide a brief summary.

Problem Statement and Description

Given a Min Heap and a target value k, the task is to identify and print all nodes in the Min Heap that have values less than k. In essence, we are required to traverse the heap and output the nodes that are smaller than the specified value k, while adhering to the Min Heap property.

Example

Consider the Min Heap depicted below:

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

For a given target value k = 10, the nodes with values less than 10 are 7, 4, 6, 2, 8, 9, 1, 3, and 5. The expected output is 7 4 6 2 8 9 1 3 5.

Approach

The central idea for solving this problem entails traversing the Min Heap in an in-order manner while considering the values of the nodes. Since in a Min Heap, parent nodes are always smaller than their children, we can efficiently decide whether to explore 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

Algorithm Explanation

  1. Create a class Node to represent a node in the Min Heap, with attributes left, right, and key.
  2. Develop a class MinHeap with attributes size and root. The root attribute points to the root of the Min Heap, and size tracks the number of nodes.
  3. 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.
  4. In the main function, instantiate a MinHeap, perform insertions to construct the Min Heap, and define the value of k.
  5. Call the printNodesLessThanK function with the root node of the Min Heap and value k.

Code Solution

/*
  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

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the Min Heap. This is due to each node being visited exactly once during traversal, and the operations executed at each node taking constant time. Consequently, the time complexity scales linearly with the number of nodes in the Min Heap.

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