Print all the leaf nodes of binary heap
In computer science, a binary heap is a specialized tree-based data structure that satisfies the heap property. Binary heaps are commonly used to implement priority queues and can be visualized as a complete binary tree, where each node has a value that is less than or equal to the values of its children (in a min heap). In this article, we'll explore how to print all the leaf nodes of a binary heap using a C program.
Problem Statement
The problem is to print all the leaf nodes of a given binary heap. A leaf node is a node in the binary heap that does not have any children.
Example
Build min heap using following array : [4 , 7 , 8 , 2 , 9 , 3 , 1 , 6 , 10]
Consider the following binary heap:
1
/ \
/ \
2 3
/ \ / \
6 9 4 8
/ \
7 10
The leaf nodes of this binary heap are: 7, 10, 9, 4, and 8.
Idea to Solve the Problem
To solve this problem, we can use a recursive approach. We will traverse the binary heap starting from the root node and recursively visit its left and right children. When we encounter a node that does not have any children (i.e., a leaf node), we will print its value.
Pseudocode
function printLeafNodes(node, size, root):
if root < size:
if left child of root is out of bounds and right child of root is out of bounds:
print value of node[root]
recursively call printLeafNodes for left child of root
recursively call printLeafNodes for right child of root
buildMinHeap(arr, size) // Constructs the min heap
printLeafNodes(arr, size, 0) // Prints leaf nodes
Algorithm Explanation
- We start by constructing the min heap using the
buildMinHeap
function, which rearranges the array elements to satisfy the min heap property. - Next, we call the
printLeafNodes
function with the arrayarr
, its sizesize
, and the root index0
. - Inside the
printLeafNodes
function, we check if the currentroot
is within bounds. If it is not, we return. - If the left child and right child of the current
root
are out of bounds (i.e., there are no children), we print the value of the currentnode[root]
. - We then recursively call the
printLeafNodes
function for the left child and the right child of the currentroot
. - The recursive calls continue until we have visited all the nodes in the heap.
Code Solution
// 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
Time Complexity
The time complexity of constructing the min heap using buildMinHeap
is O(n), where n is the number of
elements in the heap. The time complexity of printing the leaf nodes using printLeafNodes
is also O(n),
as each node is visited exactly once. Therefore, the overall time complexity of the program is O(n).
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