Skip to main content

Print all the leaf nodes of binary heap

Here given code implementation process.

// C Program
// Print all the leaf nodes of binary heap
#include <stdio.h>

//Swap two element in array
void swap(int arr[], int first, int second)
{
	int auxiliary = arr[first];
	arr[first] = arr[second];
	arr[second] = auxiliary;
}
// This is converting given root and its leaf into a valid min heap form
void minHeap(int arr[], int size, int root)
{
	int left = 2 *root + 1;
	int right = 2 *root + 2;
	int task = -1;
	if (left < size && arr[left] < arr[root])
	{
		if (right < size && arr[right] < arr[left])
		{
			// When right child is less than left child
			swap(arr, right, root);
			task = right;
		}
		else
		{
			// When left child is less than root node
			swap(arr, left, root);
			task = left;
		}
	}
	else if (right < size && arr[right] < arr[root])
	{
		// When right child is less than root node
		swap(arr, right, root);
		task = right;
	}
	if (task != -1)
	{
		// Execute function until when changes are required
		minHeap(arr, size, task);
	}
}
// Show array elements
void printData(int arr[], int size)
{
	printf("\n");
	for (int i = 0; i < size; i++)
	{
		printf("%3d", arr[i]);
	}
}
// Display leaf nodes
void leafNodes(int node[], int size, int root)
{
	if (root < size)
	{
		if ((2 *root + 1) >= size && (2 *root + 2) >= size)
		{
			printf("%3d", node[root]);
		}
		// Recursive visit to child node
		leafNodes(node, size, 2 *root + 1);
		leafNodes(node, size, 2 *root + 2);
	}
}
// Handles the request of construct min heap in given array
void buildMinHeap(int arr[], int size)
{
	for (int i = (size / 2); i >= 0; i--)
	{
		minHeap(arr, size, i);
	}
}
int main()
{
	// Array elements
	int arr[] = {
		4 , 7 , 8 , 2 , 9 , 3 , 1 , 6 , 10
	};
	// Find number of element in array
	int size = sizeof(arr) / sizeof(arr[0]);
	buildMinHeap(arr, size);
	/*
	    Construct Min heap

	          1
	        /   \
	       /     \
	      2       3
	     /  \    /  \
	    6    9  4    8
	   / \   
	  7   10 
	*/
	printf("\n Construct Min Heap ");
	//Display heap elements
	printData(arr, size);
	printf("\n Leaf nodes \n");
	leafNodes(arr, size, 0);
	return 0;
}

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7 10
 Leaf nodes
  7 10  9  4  8
/*
  Java program
  Print all the leaf nodes of binary heap
*/
public class MinHeap
{
	//Swap two element in array
	public void swap(int[] arr, int first, int second)
	{
		int auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	public void minHeap(int[] arr, int size, int root)
	{
		int left = 2 * root + 1;
		int right = 2 * root + 2;
		int task = -1;
		if (left < size && arr[left] < arr[root])
		{
			if (right < size && arr[right] < arr[left])
			{
				// When right child is less than left child
				swap(arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				swap(arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr[right] < arr[root])
		{
			// When right child is less than root node
			swap(arr, right, root);
			task = right;
		}
		if (task != -1)
		{
			// Execute function until when changes are required
			minHeap(arr, size, task);
		}
	}
	// Show array elements
	public void printData(int[] arr, int size)
	{
		System.out.print("\n");
		for (int i = 0; i < size; i++)
		{
			System.out.print("  " + arr[i]);
		}
	}
	// Display leaf nodes
	public void leafNodes(int[] node, int size, int root)
	{
		if (root < size)
		{
			if ((2 * root + 1) >= size && (2 * root + 2) >= size)
			{
				System.out.print("  " + node[root]);
			}
			// Recursive visit to child node
			leafNodes(node, size, 2 * root + 1);
			leafNodes(node, size, 2 * root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	public void buildMinHeap(int[] arr, int size)
	{
		for (int i = (size / 2); i >= 0; i--)
		{
			minHeap(arr, size, i);
		}
	}
	public static void main(String[] args)
	{
		MinHeap task = new MinHeap();
		// Array elements
		int[] arr = {
			4 , 7 , 8 , 2 , 9 , 3 , 1 , 6 , 10
		};
		// Find number of element in array
		int size = arr.length;
		task.buildMinHeap(arr, size);
		/*
		    Construct Min heap

		          1
		        /   \
		       /     \
		      2       3
		     /  \    /  \
		    6    9  4    8
		   / \   
		  7   10 
		*/
		System.out.print("\n Construct Min Heap ");
		//Display heap elements
		task.printData(arr, size);
		System.out.print("\n Leaf nodes \n");
		task.leafNodes(arr, size, 0);
	}
}

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8
// Include header file
#include <iostream>

using namespace std;
/*
  C++ program
  Print all the leaf nodes of binary heap
*/
class MinHeap
{
	public:
		//Swap two element in array
		void swap(int arr[], int first, int second)
		{
			int auxiliary = arr[first];
			arr[first] = arr[second];
			arr[second] = auxiliary;
		}
	// This is converting given root and its leaf into a valid min heap form
	void minHeap(int arr[], int size, int root)
	{
		int left = 2 *root + 1;
		int right = 2 *root + 2;
		int task = -1;
		if (left < size && arr[left] < arr[root])
		{
			if (right < size && arr[right] < arr[left])
			{
				// When right child is less than left child
				this->swap(arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				this->swap(arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr[right] < arr[root])
		{
			// When right child is less than root node
			this->swap(arr, right, root);
			task = right;
		}
		if (task != -1)
		{
			// Execute function until when changes are required
			this->minHeap(arr, size, task);
		}
	}
	// Show array elements
	void printData(int arr[], int size)
	{
		cout << "\n";
		for (int i = 0; i < size; i++)
		{
			cout << "  " << arr[i];
		}
	}
	// Display leaf nodes
	void leafNodes(int node[], int size, int root)
	{
		if (root < size)
		{
			if ((2 *root + 1) >= size && (2 *root + 2) >= size)
			{
				cout << "  " << node[root];
			}
			// Recursive visit to child node
			this->leafNodes(node, size, 2 *root + 1);
			this->leafNodes(node, size, 2 *root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	void buildMinHeap(int arr[], int size)
	{
		for (int i = (size / 2); i >= 0; i--)
		{
			this->minHeap(arr, size, i);
		}
	}
};
int main()
{
	MinHeap task = MinHeap();
	// Array elements
	int arr[] = {
		4 , 7 , 8 , 2 , 9 , 3 , 1 , 6 , 10
	};
	// Find number of element in array
	int size = sizeof(arr) / sizeof(arr[0]);
	task.buildMinHeap(arr, size);
	/*
	    Construct Min heap
	          1
	        /   \
	       /     \
	      2       3
	     /  \    /  \
	    6    9  4    8
	   / \   
	  7   10 
	*/
	cout << "\n Construct Min Heap ";
	//Display heap elements
	task.printData(arr, size);
	cout << "\n Leaf nodes \n";
	task.leafNodes(arr, size, 0);
	return 0;
}

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8
// Include namespace system
using System;
/*
  C# program
  Print all the leaf nodes of binary heap
*/
public class MinHeap
{
	//Swap two element in array
	public void swap(int[] arr, int first, int second)
	{
		int auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	public void minHeap(int[] arr, int size, int root)
	{
		int left = 2 * root + 1;
		int right = 2 * root + 2;
		int task = -1;
		if (left < size && arr[left] < arr[root])
		{
			if (right < size && arr[right] < arr[left])
			{
				// When right child is less than left child
				swap(arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				swap(arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr[right] < arr[root])
		{
			// When right child is less than root node
			swap(arr, right, root);
			task = right;
		}
		if (task != -1)
		{
			// Execute function until when changes are required
			minHeap(arr, size, task);
		}
	}
	// Show array elements
	public void printData(int[] arr, int size)
	{
		Console.Write("\n");
		for (int i = 0; i < size; i++)
		{
			Console.Write("  " + arr[i]);
		}
	}
	// Display leaf nodes
	public void leafNodes(int[] node, int size, int root)
	{
		if (root < size)
		{
			if ((2 * root + 1) >= size && (2 * root + 2) >= size)
			{
				Console.Write("  " + node[root]);
			}
			// Recursive visit to child node
			leafNodes(node, size, 2 * root + 1);
			leafNodes(node, size, 2 * root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	public void buildMinHeap(int[] arr, int size)
	{
		for (int i = (size / 2); i >= 0; i--)
		{
			minHeap(arr, size, i);
		}
	}
	public static void Main(String[] args)
	{
		MinHeap task = new MinHeap();
		// Array elements
		int[] arr = {
			4 , 7 , 8 , 2 , 9 , 3 , 1 , 6 , 10
		};
		// Find number of element in array
		int size = arr.Length;
		task.buildMinHeap(arr, size);
		/*
		    Construct Min heap
		          1
		        /   \
		       /     \
		      2       3
		     /  \    /  \
		    6    9  4    8
		   / \   
		  7   10 
		*/
		Console.Write("\n Construct Min Heap ");
		//Display heap elements
		task.printData(arr, size);
		Console.Write("\n Leaf nodes \n");
		task.leafNodes(arr, size, 0);
	}
}

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8
<?php
/*
  Php program
  Print all the leaf nodes of binary heap
*/
class MinHeapTree
{
	//Swap two element in array
	public	function swap( & $arr, $first, $second)
	{
		$auxiliary = $arr[$first];
		$arr[$first] = $arr[$second];
		$arr[$second] = $auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	public	function minHeap( & $arr, $size, $root)
	{
		$left = 2 * $root + 1;
		$right = 2 * $root + 2;
		$task = -1;
		if ($left < $size && $arr[$left] < $arr[$root])
		{
			if ($right < $size && $arr[$right] < $arr[$left])
			{
				// When right child is less than left child
				$this->swap($arr, $right, $root);
				$task = $right;
			}
			else
			{
				// When left child is less than root node
				$this->swap($arr, $left, $root);
				$task = $left;
			}
		}
		else if ($right < $size && $arr[$right] < $arr[$root])
		{
			// When right child is less than root node
			$this->swap($arr, $right, $root);
			$task = $right;
		}
		if ($task != -1)
		{
			// Execute function until when changes are required
			$this->minHeap($arr, $size, $task);
		}
	}
	// Show array elements
	public	function printData( & $arr, $size)
	{
		echo "\n";
		for ($i = 0; $i < $size; $i++)
		{
			echo "  ". $arr[$i];
		}
	}
	// Display leaf nodes
	public	function leafNodes( & $node, $size, $root)
	{
		if ($root < $size)
		{
			if ((2 * $root + 1) >= $size && (2 * $root + 2) >= $size)
			{
				echo "  ". $node[$root];
			}
			// Recursive visit to child node
			$this->leafNodes($node, $size, 2 * $root + 1);
			$this->leafNodes($node, $size, 2 * $root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	public	function buildMinHeap( & $arr, $size)
	{
		for ($i = (intval($size / 2)); $i >= 0; $i--)
		{
			$this->minHeap($arr, $size, $i);
		}
	}
}

function main()
{
	$task = new MinHeapTree();
	// Array elements
	$arr = array(4, 7, 8, 2, 9, 3, 1, 6, 10);
	// Find number of element in array
	$size = count($arr);
	$task->buildMinHeap($arr, $size);
	/*
	    Construct Min heap
	          1
	        /   \
	       /     \
	      2       3
	     /  \    /  \
	    6    9  4    8
	   / \   
	  7   10 
	*/
	echo "\n Construct Min Heap ";
	//Display heap elements
	$task->printData($arr, $size);
	echo "\n Leaf nodes \n";
	$task->leafNodes($arr, $size, 0);
}
main();

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8
/*
  Node Js program
  Print all the leaf nodes of binary heap
*/
class MinHeapTree
{
	//Swap two element in array
	swap(arr, first, second)
	{
		var auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	minHeap(arr, size, root)
	{
		var left = 2 * root + 1;
		var right = 2 * root + 2;
		var task = -1;
		if (left < size && arr[left] < arr[root])
		{
			if (right < size && arr[right] < arr[left])
			{
				// When right child is less than left child
				this.swap(arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				this.swap(arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr[right] < arr[root])
		{
			// When right child is less than root node
			this.swap(arr, right, root);
			task = right;
		}
		if (task != -1)
		{
			// Execute function until when changes are required
			this.minHeap(arr, size, task);
		}
	}
	// Show array elements
	printData(arr, size)
	{
		process.stdout.write("\n");
		for (var i = 0; i < size; i++)
		{
			process.stdout.write("  " + arr[i]);
		}
	}
	// Display leaf nodes
	leafNodes(node, size, root)
	{
		if (root < size)
		{
			if ((2 * root + 1) >= size && (2 * root + 2) >= size)
			{
				process.stdout.write("  " + node[root]);
			}
			// Recursive visit to child node
			this.leafNodes(node, size, 2 * root + 1);
			this.leafNodes(node, size, 2 * root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	buildMinHeap(arr, size)
	{
		for (var i = (parseInt(size / 2)); i >= 0; i--)
		{
			this.minHeap(arr, size, i);
		}
	}
}

function main()
{
	var task = new MinHeapTree();
	// Array elements
	var arr = [4, 7, 8, 2, 9, 3, 1, 6, 10];
	// Find number of element in array
	var size = arr.length;
	task.buildMinHeap(arr, size);
	/*
	    Construct Min heap
	          1
	        /   \
	       /     \
	      2       3
	     /  \    /  \
	    6    9  4    8
	   / \   
	  7   10 
	*/
	process.stdout.write("\n Construct Min Heap ");
	//Display heap elements
	task.printData(arr, size);
	process.stdout.write("\n Leaf nodes \n");
	task.leafNodes(arr, size, 0);
}
main();

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8
#   Python 3 program
#   Print all the leaf nodes of binary heap

class MinHeapTree :
	# Swap two element in array
	def swap(self, arr, first, second) :
		auxiliary = arr[first]
		arr[first] = arr[second]
		arr[second] = auxiliary
	
	#  This is converting given root and its leaf into a valid min heap form
	def minHeap(self, arr, size, root) :
		left = 2 * root + 1
		right = 2 * root + 2
		task = -1
		if (left < size and arr[left] < arr[root]) :
			if (right < size and arr[right] < arr[left]) :
				#  When right child is less than left child
				self.swap(arr, right, root)
				task = right
			else :
				#  When left child is less than root node
				self.swap(arr, left, root)
				task = left
			
		
		elif(right < size and arr[right] < arr[root]) :
			#  When right child is less than root node
			self.swap(arr, right, root)
			task = right
		
		if (task != -1) :
			#  Execute function until when changes are required
			self.minHeap(arr, size, task)
		
	
	#  Show array elements
	def printData(self, arr, size) :
		print(end = "\n")
		i = 0
		while (i < size) :
			print("  ", arr[i], end = "")
			i += 1
		
	
	#  Display leaf nodes
	def leafNodes(self, node, size, root) :
		if (root < size) :
			if ((2 * root + 1) >= size and(2 * root + 2) >= size) :
				print("  ", node[root], end = "")
			
			#  Recursive visit to child node
			self.leafNodes(node, size, 2 * root + 1)
			self.leafNodes(node, size, 2 * root + 2)
		
	
	#  Handles the request of construct min heap in given array
	def buildMinHeap(self, arr, size) :
		i = (int(size / 2))
		while (i >= 0) :
			self.minHeap(arr, size, i)
			i -= 1
		
	

def main() :
	task = MinHeapTree()
	#  Array elements
	arr = [4, 7, 8, 2, 9, 3, 1, 6, 10]
	#  Find number of element in array
	size = len(arr)
	task.buildMinHeap(arr, size)
	# 
	#     Construct Min heap
	#           1
	#         /   \
	#        /     \
	#       2       3
	#      /  \    /  \
	#     6    9  4    8
	#    / \   
	#   7   10 
	
	print("\n Construct Min Heap ", end = "")
	# Display heap elements
	task.printData(arr, size)
	print("\n Leaf nodes ")
	task.leafNodes(arr, size, 0)

if __name__ == "__main__": main()

Output

 Construct Min Heap
   1   2   3   6   9   4   8   7   10
 Leaf nodes
   7   10   9   4   8
#   Ruby program
#   Print all the leaf nodes of binary heap

class MinHeapTree 
	# Swap two element in array
	def swap(arr, first, second) 
		auxiliary = arr[first]
		arr[first] = arr[second]
		arr[second] = auxiliary
	end

	#  This is converting given root and its leaf into a valid min heap form
	def minHeap(arr, size, root) 
		left = 2 * root + 1
		right = 2 * root + 2
		task = -1
		if (left < size && arr[left] < arr[root]) 
			if (right < size && arr[right] < arr[left]) 
				#  When right child is less than left child
				self.swap(arr, right, root)
				task = right
			else 
				#  When left child is less than root node
				self.swap(arr, left, root)
				task = left
			end

		elsif(right < size && arr[right] < arr[root]) 
			#  When right child is less than root node
			self.swap(arr, right, root)
			task = right
		end

		if (task != -1) 
			#  Execute function until when changes are required
			self.minHeap(arr, size, task)
		end

	end

	#  Show array elements
	def printData(arr, size) 
		print("\n")
		i = 0
		while (i < size) 
			print("  ", arr[i])
			i += 1
		end

	end

	#  Display leaf nodes
	def leafNodes(node, size, root) 
		if (root < size) 
			if ((2 * root + 1) >= size && (2 * root + 2) >= size) 
				print("  ", node[root])
			end

			#  Recursive visit to child node
			self.leafNodes(node, size, 2 * root + 1)
			self.leafNodes(node, size, 2 * root + 2)
		end

	end

	#  Handles the request of construct min heap in given array
	def buildMinHeap(arr, size) 
		i = (size / 2)
		while (i >= 0) 
			self.minHeap(arr, size, i)
			i -= 1
		end

	end

end

def main() 
	task = MinHeapTree.new()
	#  Array elements
	arr = [4, 7, 8, 2, 9, 3, 1, 6, 10]
	#  Find number of element in array
	size = arr.length
	task.buildMinHeap(arr, size)
	# 
	#     Construct Min heap
	#           1
	#         /   \
	#        /     \
	#       2       3
	#      /  \    /  \
	#     6    9  4    8
	#    / \   
	#   7   10 
	
	print("\n Construct Min Heap ")
	# Display heap elements
	task.printData(arr, size)
	print("\n Leaf nodes \n")
	task.leafNodes(arr, size, 0)
end

main()

Output

 Construct Min Heap 
  1  2  3  6  9  4  8  7  10
 Leaf nodes 
  7  10  9  4  8
/*
  Scala program
  Print all the leaf nodes of binary heap
*/
class MinHeapTree
{
	//Swap two element in array
	def swap(arr: Array[Int], first: Int, second: Int): Unit = {
		var auxiliary: Int = arr(first);
		arr(first) = arr(second);
		arr(second) = auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	def minHeap(arr: Array[Int], size: Int, root: Int): Unit = {
		var left: Int = 2 * root + 1;
		var right: Int = 2 * root + 2;
		var task: Int = -1;
		if (left < size && arr(left) < arr(root))
		{
			if (right < size && arr(right) < arr(left))
			{
				// When right child is less than left child
				this.swap(arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				this.swap(arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr(right) < arr(root))
		{
			// When right child is less than root node
			this.swap(arr, right, root);
			task = right;
		}
		if (task != -1)
		{
			// Execute function until when changes are required
			this.minHeap(arr, size, task);
		}
	}
	// Show array elements
	def printData(arr: Array[Int], size: Int): Unit = {
		print("\n");
		var i: Int = 0;
		while (i < size)
		{
			print("  " + arr(i));
			i += 1;
		}
	}
	// Display leaf nodes
	def leafNodes(node: Array[Int], size: Int, root: Int): Unit = {
		if (root < size)
		{
			if ((2 * root + 1) >= size && (2 * root + 2) >= size)
			{
				print("  " + node(root));
			}
			// Recursive visit to child node
			this.leafNodes(node, size, 2 * root + 1);
			this.leafNodes(node, size, 2 * root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	def buildMinHeap(arr: Array[Int], size: Int): Unit = {
		var i: Int = ((size / 2).toInt);
		while (i >= 0)
		{
			this.minHeap(arr, size, i);
			i -= 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: MinHeapTree = new MinHeapTree();
		// Array elements
		var arr: Array[Int] = Array(4, 7, 8, 2, 9, 3, 1, 6, 10);
		// Find number of element in array
		var size: Int = arr.length;
		task.buildMinHeap(arr, size);
		/*
		    Construct Min heap
		          1
		        /   \
		       /     \
		      2       3
		     /  \    /  \
		    6    9  4    8
		   / \   
		  7   10 
		*/
		print("\n Construct Min Heap ");
		//Display heap elements
		task.printData(arr, size);
		print("\n Leaf nodes \n");
		task.leafNodes(arr, size, 0);
	}
}

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8
/*
  Swift 4 program
  Print all the leaf nodes of binary heap
*/
class MinHeapTree
{
	//Swap two element in array
	func swap(_ arr: inout[Int], _ first: Int, _ second: Int)
	{
		let auxiliary: Int = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	func minHeap(_ arr: inout[Int], _ size: Int, _ root: Int)
	{
		let left: Int = 2 * root + 1;
		let right: Int = 2 * root + 2;
		var task: Int = -1;
		if (left < size && arr[left] < arr[root])
		{
			if (right < size && arr[right] < arr[left])
			{
				// When right child is less than left child
				self.swap(&arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				self.swap(&arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr[right] < arr[root])
		{
			// When right child is less than root node
			self.swap(&arr, right, root);
			task = right;
		}
		if (task  != -1)
		{
			// Execute function until when changes are required
			self.minHeap(&arr, size, task);
		}
	}
	// Show array elements
	func printData(_ arr: [Int], _ size: Int)
	{
		print(terminator: "\n");
		var i: Int = 0;
		while (i < size)
		{
			print("  ", arr[i], terminator: "");
			i += 1;
		}
	}
	// Display leaf nodes
	func leafNodes(_ node: [Int], _ size: Int, _ root: Int)
	{
		if (root < size)
		{
			if ((2 * root + 1) >= size && (2 * root + 2) >= size)
			{
				print("  ", node[root], terminator: "");
			}
			// Recursive visit to child node
			self.leafNodes(node, size, 2 * root + 1);
			self.leafNodes(node, size, 2 * root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	func buildMinHeap(_ arr: inout[Int], _ size: Int)
	{
		var i: Int = (size / 2);
		while (i >= 0)
		{
			self.minHeap(&arr, size, i);
			i -= 1;
		}
	}
}
func main()
{
	let task: MinHeapTree = MinHeapTree();
	// Array elements
	var arr: [Int] = [4, 7, 8, 2, 9, 3, 1, 6, 10];
	// Find number of element in array
	let size: Int = arr.count;
	task.buildMinHeap(&arr, size);
	/*
	    Construct Min heap
	          1
	        /   \
	       /     \
	      2       3
	     /  \    /  \
	    6    9  4    8
	   / \   
	  7   10 
	*/
	print("\n Construct Min Heap ", terminator: "");
	//Display heap elements
	task.printData(arr, size);
	print("\n Leaf nodes ");
	task.leafNodes(arr, size, 0);
}
main();

Output

 Construct Min Heap
   1   2   3   6   9   4   8   7   10
 Leaf nodes
   7   10   9   4   8
/*
  Kotlin program
  Print all the leaf nodes of binary heap
*/
class MinHeapTree
{
	//Swap two element in array
	fun swap(arr: Array <Int> , first: Int, second: Int): Unit
	{
		var auxiliary: Int = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	fun minHeap(arr: Array <Int> , size: Int, root: Int): Unit
	{
		var left: Int = 2 * root + 1;
		var right: Int = 2 * root + 2;
		var task: Int = -1;
		if (left < size && arr[left] < arr[root])
		{
			if (right < size && arr[right] < arr[left])
			{
				// When right child is less than left child
				this.swap(arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				this.swap(arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr[right] < arr[root])
		{
			// When right child is less than root node
			this.swap(arr, right, root);
			task = right;
		}
		if (task != -1)
		{
			// Execute function until when changes are required
			this.minHeap(arr, size, task);
		}
	}
	// Show array elements
	fun printData(arr: Array < Int > , size: Int): Unit
	{
		print("\n");
		var i: Int = 0;
		while (i < size)
		{
			print("  " + arr[i]);
			i += 1;
		}
	}
	// Display leaf nodes
	fun leafNodes(node: Array < Int > , size: Int, root: Int): Unit
	{
		if (root < size)
		{
			if ((2 * root + 1) >= size && (2 * root + 2) >= size)
			{
				print("  " + node[root]);
			}
			// Recursive visit to child node
			this.leafNodes(node, size, 2 * root + 1);
			this.leafNodes(node, size, 2 * root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	fun buildMinHeap(arr: Array < Int > , size: Int): Unit
	{
		var i: Int = (size / 2);
		while (i >= 0)
		{
			this.minHeap(arr, size, i);
			i -= 1;
		}
	}
}
fun main(args: Array <String> ): Unit
{
	var task: MinHeapTree = MinHeapTree();
	// Array elements
	var arr: Array <Int> = arrayOf(4, 7, 8, 2, 9, 3, 1, 6, 10);
	// Find number of element in array
	var size: Int = arr.count();
	task.buildMinHeap(arr, size);
	/*
	    Construct Min heap
	          1
	        /   \
	       /     \
	      2       3
	     /  \    /  \
	    6    9  4    8
	   / \   
	  7   10 
	*/
	print("\n Construct Min Heap ");
	//Display heap elements
	task.printData(arr, size);
	print("\n Leaf nodes \n");
	task.leafNodes(arr, size, 0);
}

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8




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