Skip to main content

Ternary Max heap

A Ternary Max Heap is a data structure that is similar to a binary max heap, but with three children nodes for each parent node instead of two. In a Ternary Max Heap, each node has at most three children, and the value of each node is greater than or equal to the values of its children.

The first level of the Ternary Max Heap has only one node, the second level has three nodes, the third level has nine nodes, and so on. The height of the Ternary Max Heap is log3(n), where n is the number of nodes.

Ternary Max Heap is a complete binary tree, and it is similar to binary heap properties. The Ternary Max Heap has some advantages over a binary max heap, such as better memory utilization and fewer swaps during heap operations like insertion and deletion. However, it is not commonly used in practice due to its complex implementation and lack of significant performance advantages.

Here given code implementation process.

/*
  C Program 
  Ternary Max heap
*/
#include <stdio.h>

// Display pre order view of ternary tree
void preorder(int node[], int size, int root)
{
	if (root < size)
	{
		printf("%3d", node[root]);
		// Recursive visit to child node
		preorder(node, size, 3 *root + 1);
		preorder(node, size, 3 *root + 2);
		preorder(node, size, 3 *root + 3);
	}
}
//Swap two element in array
void swap(int node[], int first, int second)
{
	int auxiliary = node[first];
	node[first] = node[second];
	node[second] = auxiliary;
}
// Compare tree node and convert into valid max heap
int compare(int node[], int root, int size)
{
	int location = -1;
	for (int i = 1; i <= 3; ++i)
	{
		if (3 *root + i < size && node[3 *root + i] > node[root])
		{
			if (location == -1)
			{
				location = 3 *root + i;
			}
			else if (node[3 *root + i] > node[location])
			{
				location = 3 *root + i;
			}
		}
	}
	if (location != -1)
	{
		// When node value are change
		swap(node, root, location);
	}
	return location;
}
// Convert into max heap
void heap(int node[], int size, int root)
{
	int task = compare(node, root, size);
	if (task != -1)
	{
		// Recursively execute function, when tasks are remain
		heap(node, size, task);
	}
}
// Handles the request of constructing ternary max heap
void makeTernaryHeap(int node[], int size)
{
	for (int i = (size / 3); i >= 0; i--)
	{
		heap(node, size, i);
	}
}
int main()
{
	// Tree nodes
	int node[] = {
		10 , 7 , 2 , 9 , 1 , 4 , 6 , 3 , 8 , 5 , 11
	};
	// Get the number of elements
	int size = sizeof(node) / sizeof(node[0]);
	// Construct Max heap
	makeTernaryHeap(node, size);
	/*Max heap
	-----------------------   
	              11
	            / | \  
	           /  |  \  
	          /   |   \
	         /    |    \
	        /     |     \
	       /      |      \
	      /       |       \
	     /        |        \
	    7         8         10
	  / |  \    / | \      /
	 1  4   6  3  2  5    9
	----------------------------
	        Constructed Tree               
	*/
	printf(" Preorder\n");
	preorder(node, size, 0);
	return 0;
}

Output

 Preorder
 11  7  1  4  6  8  3  2  5 10  9
/*
 Java program
 Implement Ternary Max heap
*/
public class TernaryMaxHeap
{
    // Display pre order view of ternary tree
    public void preorder(int[] node, int size, int root)
    {
        if (root < size)
        {
            System.out.print("  " + node[root]);
            // Recursive visit to child node
            preorder(node, size, 3 * root + 1);
            preorder(node, size, 3 * root + 2);
            preorder(node, size, 3 * root + 3);
        }
    }
    //Swap two element in array
    public void swap(int[] node, int first, int second)
    {
        int auxiliary = node[first];
        node[first] = node[second];
        node[second] = auxiliary;
    }
    // Compare tree node and convert into valid min heap
    public int compare(int[] node, int root, int size)
    {
        int location = -1;
        for (int i = 1; i <= 3; ++i)
        {
            if (3 * root + i < size && node[3 * root + i] > node[root])
            {
                if (location == -1)
                {
                    location = 3 * root + i;
                }
                else if (node[3 * root + i] > node[location])
                {
                    location = 3 * root + i;
                }
            }
        }
        if (location != -1)
        {
            // When node value are change
            swap(node, root, location);
        }
        return location;
    }
    // Convert into min heap
    public void heap(int[] node, int size, int root)
    {
        int task = compare(node, root, size);
        if (task != -1)
        {
            // Recursively execute function, when tasks are remain
            heap(node, size, task);
        }
    }
    // Handles the request of constructing ternary min heap
    public void makeTernaryHeap(int[] node, int size)
    {
        for (int i = (size / 3); i >= 0; i--)
        {
            heap(node, size, i);
        }
    }
    public static void main(String[] args)
    {
        TernaryMaxHeap task = new TernaryMaxHeap();
        // Tree nodes
        int[] node = {
            10 , 7 , 2 , 9 , 1 , 4 , 6 , 3 , 8 , 5 , 11
        };
        // Get the number of elements
        int size = node.length;
        // Construct Max heap
        task.makeTernaryHeap(node, size);
        /* Max heap
        -----------------------   
                      11
                    / | \  
                   /  |  \  
                  /   |   \
                 /    |    \
                /     |     \
               /      |      \
              /       |       \
             /        |        \
            7         8         10
          / |  \    / | \      /
         1  4   6  3  2  5    9
        ----------------------------
                Constructed Tree               
        */
        System.out.print(" Preorder\n");
        task.preorder(node, size, 0);
    }
}

Output

 Preorder
  11  7  1  4  6  8  3  2  5  10  9
// Include header file
#include <iostream>

using namespace std;
/*
 C++ program
 Implement Ternary Max heap
*/
class TernaryMaxHeap
{
	public:
		// Display pre order view of ternary tree
		void preorder(int node[], int size, int root)
		{
			if (root < size)
			{
				cout << "  " << node[root];
				// Recursive visit to child node
				this->preorder(node, size, 3 *root + 1);
				this->preorder(node, size, 3 *root + 2);
				this->preorder(node, size, 3 *root + 3);
			}
		}
	//Swap two element in array
	void swap(int node[], int first, int second)
	{
		int auxiliary = node[first];
		node[first] = node[second];
		node[second] = auxiliary;
	}
	// Compare tree node and convert into valid min heap
	int compare(int node[], int root, int size)
	{
		int location = -1;
		for (int i = 1; i <= 3; ++i)
		{
			if (3 *root + i < size && node[3 *root + i] > node[root])
			{
				if (location == -1)
				{
					location = 3 *root + i;
				}
				else if (node[3 *root + i] > node[location])
				{
					location = 3 *root + i;
				}
			}
		}
		if (location != -1)
		{
			// When node value are change
			this->swap(node, root, location);
		}
		return location;
	}
	// Convert into min heap
	void heap(int node[], int size, int root)
	{
		int task = this->compare(node, root, size);
		if (task != -1)
		{
			// Recursively execute function, when tasks are remain
			this->heap(node, size, task);
		}
	}
	// Handles the request of constructing ternary min heap
	void makeTernaryHeap(int node[], int size)
	{
		for (int i = (size / 3); i >= 0; i--)
		{
			this->heap(node, size, i);
		}
	}
};
int main()
{
	TernaryMaxHeap task = TernaryMaxHeap();
	// Tree nodes
	int node[] = {
		10 , 7 , 2 , 9 , 1 , 4 , 6 , 3 , 8 , 5 , 11
	};
	// Get the number of elements
	int size = sizeof(node) / sizeof(node[0]);
	// Construct Max heap
	task.makeTernaryHeap(node, size);
	/*Max heap
	-----------------------   
	              11
	            / | \  
	           /  |  \  
	          /   |   \
	         /    |    \
	        /     |     \
	       /      |      \
	      /       |       \
	     /        |        \
	    7         8         10
	  / |  \    / | \      /
	 1  4   6  3  2  5    9
	----------------------------
	        Constructed Tree                  
	*/
	cout << " Preorder\n";
	task.preorder(node, size, 0);
	return 0;
}

Output

 Preorder
  11  7  1  4  6  8  3  2  5  10  9
// Include namespace system
using System;
/*
 C# program
 Implement Ternary Max heap
*/
public class TernaryMaxHeap
{
	// Display pre order view of ternary tree
	public void preorder(int[] node, int size, int root)
	{
		if (root < size)
		{
			Console.Write("  " + node[root]);
			// Recursive visit to child node
			preorder(node, size, 3 * root + 1);
			preorder(node, size, 3 * root + 2);
			preorder(node, size, 3 * root + 3);
		}
	}
	//Swap two element in array
	public void swap(int[] node, int first, int second)
	{
		int auxiliary = node[first];
		node[first] = node[second];
		node[second] = auxiliary;
	}
	// Compare tree node and convert into valid min heap
	public int compare(int[] node, int root, int size)
	{
		int location = -1;
		for (int i = 1; i <= 3; ++i)
		{
			if (3 * root + i < size && node[3 * root + i] > node[root])
			{
				if (location == -1)
				{
					location = 3 * root + i;
				}
				else if (node[3 * root + i] > node[location])
				{
					location = 3 * root + i;
				}
			}
		}
		if (location != -1)
		{
			// When node value are change
			swap(node, root, location);
		}
		return location;
	}
	// Convert into min heap
	public void heap(int[] node, int size, int root)
	{
		int task = compare(node, root, size);
		if (task != -1)
		{
			// Recursively execute function, when tasks are remain
			heap(node, size, task);
		}
	}
	// Handles the request of constructing ternary min heap
	public void makeTernaryHeap(int[] node, int size)
	{
		for (int i = (size / 3); i >= 0; i--)
		{
			heap(node, size, i);
		}
	}
	public static void Main(String[] args)
	{
		TernaryMaxHeap task = new TernaryMaxHeap();
		// Tree nodes
		int[] node = {
			10 , 7 , 2 , 9 , 1 , 4 , 6 , 3 , 8 , 5 , 11
		};
		// Get the number of elements
		int size = node.Length;
		// Construct Max heap
		task.makeTernaryHeap(node, size);
		/* Max heap
		-----------------------   
		              11
		            / | \  
		           /  |  \  
		          /   |   \
		         /    |    \
		        /     |     \
		       /      |      \
		      /       |       \
		     /        |        \
		    7         8         10
		  / |  \    / | \      /
		 1  4   6  3  2  5    9
		----------------------------
		        Constructed Tree                  
		*/
		Console.Write(" Preorder\n");
		task.preorder(node, size, 0);
	}
}

Output

 Preorder
  11  7  1  4  6  8  3  2  5  10  9
<?php
/*
 Php program
 Implement Ternary Max heap
*/
class TernaryMaxHeap
{
	// Display pre order view of ternary tree
	public	function preorder( & $node, $size, $root)
	{
		if ($root < $size)
		{
			echo "  ". $node[$root];
			// Recursive visit to child node
			$this->preorder($node, $size, 3 * $root + 1);
			$this->preorder($node, $size, 3 * $root + 2);
			$this->preorder($node, $size, 3 * $root + 3);
		}
	}
	//Swap two element in array
	public	function swap( & $node, $first, $second)
	{
		$auxiliary = $node[$first];
		$node[$first] = $node[$second];
		$node[$second] = $auxiliary;
	}
	// Compare tree node and convert into valid min heap
	public	function compare( & $node, $root, $size)
	{
		$location = -1;
		for ($i = 1; $i <= 3; ++$i)
		{
			if (3 * $root + $i < $size && $node[3 * $root + $i] > $node[$root])
			{
				if ($location == -1)
				{
					$location = 3 * $root + $i;
				}
				else if ($node[3 * $root + $i] > $node[$location])
				{
					$location = 3 * $root + $i;
				}
			}
		}
		if ($location != -1)
		{
			// When node value are change
			$this->swap($node, $root, $location);
		}
		return $location;
	}
	// Convert into min heap
	public	function heap( & $node, $size, $root)
	{
		$task = $this->compare($node, $root, $size);
		if ($task != -1)
		{
			// Recursively execute function, when tasks are remain
			$this->heap($node, $size, $task);
		}
	}
	// Handles the request of constructing ternary min heap
	public	function makeTernaryHeap( & $node, $size)
	{
		for ($i = (intval($size / 3)); $i >= 0; $i--)
		{
			$this->heap($node, $size, $i);
		}
	}
}

function main()
{
	$task = new TernaryMaxHeap();
	// Tree nodes
	$node = array(10, 7, 2, 9, 1, 4, 6, 3, 8, 5, 11);
	// Get the number of elements
	$size = count($node);
	// Construct Max heap
	$task->makeTernaryHeap($node, $size);
	/* Max heap
	-----------------------   
	              11
	            / | \  
	           /  |  \  
	          /   |   \
	         /    |    \
	        /     |     \
	       /      |      \
	      /       |       \
	     /        |        \
	    7         8         10
	  / |  \    / | \      /
	 1  4   6  3  2  5    9
	----------------------------
	        Constructed Tree                  
	*/
	echo " Preorder\n";
	$task->preorder($node, $size, 0);
}
main();

Output

 Preorder
  11  7  1  4  6  8  3  2  5  10  9
/*
 Node Js program
 Implement Ternary Max heap
*/
class TernaryMaxHeap
{
	// Display pre order view of ternary tree
	preorder(node, size, root)
	{
		if (root < size)
		{
			process.stdout.write("  " + node[root]);
			// Recursive visit to child node
			this.preorder(node, size, 3 * root + 1);
			this.preorder(node, size, 3 * root + 2);
			this.preorder(node, size, 3 * root + 3);
		}
	}
	//Swap two element in array
	swap(node, first, second)
	{
		var auxiliary = node[first];
		node[first] = node[second];
		node[second] = auxiliary;
	}
	// Compare tree node and convert into valid min heap
	compare(node, root, size)
	{
		var location = -1;
		for (var i = 1; i <= 3; ++i)
		{
			if (3 * root + i < size && node[3 * root + i] > node[root])
			{
				if (location == -1)
				{
					location = 3 * root + i;
				}
				else if (node[3 * root + i] > node[location])
				{
					location = 3 * root + i;
				}
			}
		}
		if (location != -1)
		{
			// When node value are change
			this.swap(node, root, location);
		}
		return location;
	}
	// Convert into min heap
	heap(node, size, root)
	{
		var task = this.compare(node, root, size);
		if (task != -1)
		{
			// Recursively execute function, when tasks are remain
			this.heap(node, size, task);
		}
	}
	// Handles the request of constructing ternary min heap
	makeTernaryHeap(node, size)
	{
		for (var i = (parseInt(size / 3)); i >= 0; i--)
		{
			this.heap(node, size, i);
		}
	}
}

function main()
{
	var task = new TernaryMaxHeap();
	// Tree nodes
	var node = [10, 7, 2, 9, 1, 4, 6, 3, 8, 5, 11];
	// Get the number of elements
	var size = node.length;
	// Construct Max heap
	task.makeTernaryHeap(node, size);
	/* Max heap
	-----------------------   
	              11
	            / | \  
	           /  |  \  
	          /   |   \
	         /    |    \
	        /     |     \
	       /      |      \
	      /       |       \
	     /        |        \
	    7         8         10
	  / |  \    / | \      /
	 1  4   6  3  2  5    9
	----------------------------
	        Constructed Tree                  
	*/
	process.stdout.write(" Preorder\n");
	task.preorder(node, size, 0);
}
main();

Output

 Preorder
  11  7  1  4  6  8  3  2  5  10  9
#  Python 3 program
#  Implement Ternary Max heap

class TernaryMaxHeap :
	#  Display pre order view of ternary tree
	def preorder(self, node, size, root) :
		if (root < size) :
			print("  ", node[root], end = "")
			#  Recursive visit to child node
			self.preorder(node, size, 3 * root + 1)
			self.preorder(node, size, 3 * root + 2)
			self.preorder(node, size, 3 * root + 3)
		
	
	# Swap two element in array
	def swap(self, node, first, second) :
		auxiliary = node[first]
		node[first] = node[second]
		node[second] = auxiliary
	
	#  Compare tree node and convert into valid min heap
	def compare(self, node, root, size) :
		location = -1
		i = 1
		while (i <= 3) :
			if (3 * root + i < size and node[3 * root + i] > node[root]) :
				if (location == -1) :
					location = 3 * root + i
				
				elif(node[3 * root + i] > node[location]) :
					location = 3 * root + i
				
			
			i += 1
		
		if (location != -1) :
			#  When node value are change
			self.swap(node, root, location)
		
		return location
	
	#  Convert into min heap
	def heap(self, node, size, root) :
		task = self.compare(node, root, size)
		if (task != -1) :
			#  Recursively execute function, when tasks are remain
			self.heap(node, size, task)
		
	
	#  Handles the request of constructing ternary min heap
	def makeTernaryHeap(self, node, size) :
		i = (int(size / 3))
		while (i >= 0) :
			self.heap(node, size, i)
			i -= 1
		
	

def main() :
	task = TernaryMaxHeap()
	#  Tree nodes
	node = [10, 7, 2, 9, 1, 4, 6, 3, 8, 5, 11]
	#  Get the number of elements
	size = len(node)
	#  Construct Max heap
	task.makeTernaryHeap(node, size)
	#  Max heap
	# -----------------------   
	#               11
	#             / | \  
	#            /  |  \  
	#           /   |   \
	#          /    |    \
	#         /     |     \
	#        /      |      \
	#       /       |       \
	#      /        |        \
	#     7         8         10
	#   / |  \    / | \      /
	#  1  4   6  3  2  5    9
	# ----------------------------
	#         Constructed Tree                  
	
	print(" Preorder")
	task.preorder(node, size, 0)

if __name__ == "__main__": main()

Output

 Preorder
   11   7   1   4   6   8   3   2   5   10   9
#  Ruby program
#  Implement Ternary Max heap

class TernaryMaxHeap 
	#  Display pre order view of ternary tree
	def preorder(node, size, root) 
		if (root < size) 
			print("  ", node[root])
			#  Recursive visit to child node
			self.preorder(node, size, 3 * root + 1)
			self.preorder(node, size, 3 * root + 2)
			self.preorder(node, size, 3 * root + 3)
		end

	end

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

	#  Compare tree node and convert into valid min heap
	def compare(node, root, size) 
		location = -1
		i = 1
		while (i <= 3) 
			if (3 * root + i < size && node[3 * root + i] > node[root]) 
				if (location == -1) 
					location = 3 * root + i
				elsif(node[3 * root + i] > node[location]) 
					location = 3 * root + i
				end

			end

			i += 1
		end

		if (location != -1) 
			#  When node value are change
			self.swap(node, root, location)
		end

		return location
	end

	#  Convert into min heap
	def heap(node, size, root) 
		task = self.compare(node, root, size)
		if (task != -1) 
			#  Recursively execute function, when tasks are remain
			self.heap(node, size, task)
		end

	end

	#  Handles the request of constructing ternary min heap
	def makeTernaryHeap(node, size) 
		i = (size / 3)
		while (i >= 0) 
			self.heap(node, size, i)
			i -= 1
		end

	end

end

def main() 
	task = TernaryMaxHeap.new()
	#  Tree nodes
	node = [10, 7, 2, 9, 1, 4, 6, 3, 8, 5, 11]
	#  Get the number of elements
	size = node.length
	#  Construct Max heap
	task.makeTernaryHeap(node, size)
	#  Max heap
	# -----------------------   
	#               11
	#             / | \  
	#            /  |  \  
	#           /   |   \
	#          /    |    \
	#         /     |     \
	#        /      |      \
	#       /       |       \
	#      /        |        \
	#     7         8         10
	#   / |  \    / | \      /
	#  1  4   6  3  2  5    9
	# ----------------------------
	#         Constructed Tree                  
	
	print(" Preorder\n")
	task.preorder(node, size, 0)
end

main()

Output

 Preorder
  11  7  1  4  6  8  3  2  5  10  9
/*
 Scala program
 Implement Ternary Max heap
*/
class TernaryMaxHeap
{
	// Display pre order view of ternary tree
	def preorder(node: Array[Int], size: Int, root: Int): Unit = {
		if (root < size)
		{
			print("  " + node(root));
			// Recursive visit to child node
			this.preorder(node, size, 3 * root + 1);
			this.preorder(node, size, 3 * root + 2);
			this.preorder(node, size, 3 * root + 3);
		}
	}
	//Swap two element in array
	def swap(node: Array[Int], first: Int, second: Int): Unit = {
		var auxiliary: Int = node(first);
		node(first) = node(second);
		node(second) = auxiliary;
	}
	// Compare tree node and convert into valid min heap
	def compare(node: Array[Int], root: Int, size: Int): Int = {
		var location: Int = -1;
		var i: Int = 1;
		while (i <= 3)
		{
			if (3 * root + i < size && node(3 * root + i) > node(root))
			{
				if (location == -1)
				{
					location = 3 * root + i;
				}
				else if (node(3 * root + i) > node(location))
				{
					location = 3 * root + i;
				}
			}
			i += 1;
		}
		if (location != -1)
		{
			// When node value are change
			this.swap(node, root, location);
		}
		return location;
	}
	// Convert into min heap
	def heap(node: Array[Int], size: Int, root: Int): Unit = {
		var task: Int = this.compare(node, root, size);
		if (task != -1)
		{
			// Recursively execute function, when tasks are remain
			this.heap(node, size, task);
		}
	}
	// Handles the request of constructing ternary min heap
	def makeTernaryHeap(node: Array[Int], size: Int): Unit = {
		var i: Int = ((size / 3).toInt);
		while (i >= 0)
		{
			this.heap(node, size, i);
			i -= 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: TernaryMaxHeap = new TernaryMaxHeap();
		// Tree nodes
		var node: Array[Int] = Array(10, 7, 2, 9, 1, 4, 6, 3, 8, 5, 11);
		// Get the number of elements
		var size: Int = node.length;
		// Construct Max heap
		task.makeTernaryHeap(node, size);
		/* Max heap
		-----------------------   
		              11
		            / | \  
		           /  |  \  
		          /   |   \
		         /    |    \
		        /     |     \
		       /      |      \
		      /       |       \
		     /        |        \
		    7         8         10
		  / |  \    / | \      /
		 1  4   6  3  2  5    9
		----------------------------
		        Constructed Tree                  
		*/
		print(" Preorder\n");
		task.preorder(node, size, 0);
	}
}

Output

 Preorder
  11  7  1  4  6  8  3  2  5  10  9
/*
 Swift 4 program
 Implement Ternary Max heap
*/
class TernaryMaxHeap
{
	// Display pre order view of ternary tree
	func preorder(_ node: [Int], _ size: Int, _ root: Int)
	{
		if (root < size)
		{
			print("  ", node[root], terminator: "");
			// Recursive visit to child node
			self.preorder(node, size, 3 * root + 1);
			self.preorder(node, size, 3 * root + 2);
			self.preorder(node, size, 3 * root + 3);
		}
	}
	//Swap two element in array
	func swap(_ node: inout[Int], _ first: Int, _ second: Int)
	{
		let auxiliary: Int = node[first];
		node[first] = node[second];
		node[second] = auxiliary;
	}
	// Compare tree node and convert into valid min heap
	func compare(_ node: inout[Int], _ root: Int, _ size: Int)->Int
	{
		var location: Int = -1;
		var i: Int = 1;
		while (i <= 3)
		{
			if (3 * root + i < size && node[3 * root + i] > node[root])
			{
				if (location == -1)
				{
					location = 3 * root + i;
				}
				else if (node[3 * root + i] > node[location])
				{
					location = 3 * root + i;
				}
			}
			i += 1;
		}
		if (location  != -1)
		{
			// When node value are change
			self.swap(&node, root, location);
		}
		return location;
	}
	// Convert into min heap
	func heap(_ node: inout[Int], _ size: Int, _ root: Int)
	{
		let task: Int = self.compare(&node, root, size);
		if (task  != -1)
		{
			// Recursively execute function, when tasks are remain
			self.heap(&node, size, task);
		}
	}
	// Handles the request of constructing ternary min heap
	func makeTernaryHeap(_ node: inout[Int], _ size: Int)
	{
		var i: Int = (size / 3);
		while (i >= 0)
		{
			self.heap(&node, size, i);
			i -= 1;
		}
	}
}
func main()
{
	let task: TernaryMaxHeap = TernaryMaxHeap();
	// Tree nodes
	var node: [Int] = [10, 7, 2, 9, 1, 4, 6, 3, 8, 5, 11];
	// Get the number of elements
	let size: Int = node.count;
	// Construct Max heap
	task.makeTernaryHeap(&node, size);
	/* Max heap
	-----------------------   
	              11
	            / | \  
	           /  |  \  
	          /   |   \
	         /    |    \
	        /     |     \
	       /      |      \
	      /       |       \
	     /        |        \
	    7         8         10
	  / |  \    / | \      /
	 1  4   6  3  2  5    9
	----------------------------
	        Constructed Tree                  
	*/
	print(" Preorder");
	task.preorder(node, size, 0);
}
main();

Output

 Preorder
   11   7   1   4   6   8   3   2   5   10   9
/*
 Kotlin program
 Implement Ternary Max heap
*/
class TernaryMaxHeap
{
	// Display pre order view of ternary tree
	fun preorder(node: Array <Int> , size: Int, root: Int): Unit
	{
		if (root < size)
		{
			print("  " + node[root]);
			// Recursive visit to child node
			this.preorder(node, size, 3 * root + 1);
			this.preorder(node, size, 3 * root + 2);
			this.preorder(node, size, 3 * root + 3);
		}
	}
	//Swap two element in array
	fun swap(node: Array <Int> , first: Int, second: Int): Unit
	{
		var auxiliary: Int = node[first];
		node[first] = node[second];
		node[second] = auxiliary;
	}
	// Compare tree node and convert into valid min heap
	fun compare(node: Array <Int> , root: Int, size: Int): Int
	{
		var location: Int = -1;
		var i: Int = 1;
		while (i <= 3)
		{
			if (3 * root + i < size && node[3 * root + i] > node[root])
			{
				if (location == -1)
				{
					location = 3 * root + i;
				}
				else if (node[3 * root + i] > node[location])
				{
					location = 3 * root + i;
				}
			}
			i += 1;
		}
		if (location != -1)
		{
			// When node value are change
			this.swap(node, root, location);
		}
		return location;
	}
	// Convert into min heap
	fun heap(node: Array <Int> , size: Int, root: Int): Unit
	{
		var task: Int = this.compare(node, root, size);
		if (task != -1)
		{
			// Recursively execute function, when tasks are remain
			this.heap(node, size, task);
		}
	}
	// Handles the request of constructing ternary min heap
	fun makeTernaryHeap(node: Array <Int> , size: Int): Unit
	{
		var i: Int = (size / 3);
		while (i >= 0)
		{
			this.heap(node, size, i);
			i -= 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: TernaryMaxHeap = TernaryMaxHeap();
	// Tree nodes
	var node: Array<Int> = arrayOf(10, 7, 2, 9, 1, 4, 6, 3, 8, 5, 11);
	// Get the number of elements
	var size: Int = node.count();
	// Construct Max heap
	task.makeTernaryHeap(node, size);
	/* Max heap
	-----------------------   
	              11
	            / | \  
	           /  |  \  
	          /   |   \
	         /    |    \
	        /     |     \
	       /      |      \
	      /       |       \
	     /        |        \
	    7         8         10
	  / |  \    / | \      /
	 1  4   6  3  2  5    9
	----------------------------
	        Constructed Tree                  
	*/
	print(" Preorder\n");
	task.preorder(node, size, 0);
}

Output

 Preorder
  11  7  1  4  6  8  3  2  5  10  9
Last updated on by Kalkicode




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