# 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);
{
// Recursively execute function, when tasks are remain
}
}
// 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);
// 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);
{
// Recursively execute function, when tasks are remain
}
}
// 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)
{
// 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
/* Max heap
-----------------------
11
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
7         8         10
/ |  \    / | \      /
1  4   6  3  2  5    9
----------------------------
Constructed Tree
*/
System.out.print(" Preorder\n");
}
}``````

#### 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);
{
// Recursively execute function, when tasks are remain
}
}
// 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()
{
// 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);
// Construct Max heap
/*Max heap
-----------------------
11
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
7         8         10
/ |  \    / | \      /
1  4   6  3  2  5    9
----------------------------
Constructed Tree
*/
cout << " Preorder\n";
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);
{
// Recursively execute function, when tasks are remain
}
}
// 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)
{
// 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
/* Max heap
-----------------------
11
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
7         8         10
/ |  \    / | \      /
1  4   6  3  2  5    9
----------------------------
Constructed Tree
*/
Console.Write(" Preorder\n");
}
}``````

#### 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)
{
{
// Recursively execute function, when tasks are remain
}
}
// 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()
{
// 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
/* Max heap
-----------------------
11
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
7         8         10
/ |  \    / | \      /
1  4   6  3  2  5    9
----------------------------
Constructed Tree
*/
echo " Preorder\n";
}
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);
{
// Recursively execute function, when tasks are remain
}
}
// 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()
{
// 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
/* Max heap
-----------------------
11
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
7         8         10
/ |  \    / | \      /
1  4   6  3  2  5    9
----------------------------
Constructed Tree
*/
process.stdout.write(" Preorder\n");
}
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) :
#  Recursively execute function, when tasks are remain

#  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() :
#  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
#  Max heap
# -----------------------
#               11
#             / | \
#            /  |  \
#           /   |   \
#          /    |    \
#         /     |     \
#        /      |      \
#       /       |       \
#      /        |        \
#     7         8         10
#   / |  \    / | \      /
#  1  4   6  3  2  5    9
# ----------------------------
#         Constructed Tree

print(" Preorder")

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)
#  Recursively execute function, when tasks are remain
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()
#  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
#  Max heap
# -----------------------
#               11
#             / | \
#            /  |  \
#           /   |   \
#          /    |    \
#         /     |     \
#        /      |      \
#       /       |       \
#      /        |        \
#     7         8         10
#   / |  \    / | \      /
#  1  4   6  3  2  5    9
# ----------------------------
#         Constructed Tree

print(" Preorder\n")
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);
{
// Recursively execute function, when tasks are remain
}
}
// 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
/* Max heap
-----------------------
11
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
7         8         10
/ |  \    / | \      /
1  4   6  3  2  5    9
----------------------------
Constructed Tree
*/
print(" Preorder\n");
}
}``````

#### 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);
{
// Recursively execute function, when tasks are remain
}
}
// 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()
{
// 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
/* Max heap
-----------------------
11
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
7         8         10
/ |  \    / | \      /
1  4   6  3  2  5    9
----------------------------
Constructed Tree
*/
print(" Preorder");
}
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);
{
// Recursively execute function, when tasks are remain
}
}
// 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
{
// 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
/* Max heap
-----------------------
11
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
7         8         10
/ |  \    / | \      /
1  4   6  3  2  5    9
----------------------------
Constructed Tree
*/
print(" Preorder\n");
}``````

#### Output

`````` Preorder
11  7  1  4  6  8  3  2  5  10  9``````

## 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.