Posted on by Kalkicode
Code Heap

# Ternary Min heap

A ternary min heap is a specialized form of a min heap data structure where each node has at most three children, and the value of each node is less than or equal to the values of its children. In other words, it is a complete binary tree where each parent node has three children and the value of each parent node is less than or equal to the values of its children.

Like any other min heap, a ternary min heap can be used to efficiently maintain a collection of items with minimum values, such as in a priority queue data structure. However, due to its structure with three children per node, a ternary min heap can have a shorter height than a binary min heap of the same size, leading to faster search and insertion times.

The main operations on a ternary min heap are insertion and deletion of the minimum element, which take O(log3 n) time, where n is the number of elements in the heap.

Here's an example of a ternary min heap tree: In this tree, each node has at most three children, and the value of each parent node is less than or equal to the values of its children. This is a ternary min heap because it satisfies the properties of a min heap, and each node has at most three children.

Here given code implementation process.

``````/*
C Program
Ternary Min 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 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
swap(node, root, location);
}
return location;
}
// Convert into min 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 min 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
};
// Get the number of elements
int size = sizeof(node) / sizeof(node);
// Construct Min heap
makeTernaryHeap(node, size);
/*Min heap
-----------------------
1
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
4         2         9
/ |  \    / | \
7  10  6  3  8  5
----------------------------
Constructed Tree
*/
printf(" Preorder\n");
preorder(node, size, 0);
return 0;
}``````

#### Output

`````` Preorder
1  4  7 10  6  2  3  8  5  9``````
``````/*
Java program
Implement Ternary Min heap
*/
public class TernaryMinHeap
{
// 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
};
// Get the number of elements
int size = node.length;
// Construct Min heap
/*Min heap
-----------------------
1
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
4         2         9
/ |  \    / | \
7  10  6  3  8  5
----------------------------
Constructed Tree
*/
System.out.print(" Preorder\n");
}
}``````

#### Output

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

using namespace std;
/*
C++ program
Implement Ternary Min heap
*/
class TernaryMinHeap
{
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
};
// Get the number of elements
int size = sizeof(node) / sizeof(node);
// Construct Min heap
/*
Min heap
-----------------------
1
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
4         2         9
/ |  \    / | \
7  10  6  3  8  5
----------------------------
Constructed Tree
*/
cout << " Preorder\n";
return 0;
}``````

#### Output

`````` Preorder
1  4  7  10  6  2  3  8  5  9``````
``````// Include namespace system
using System;
/*
C# program
Implement Ternary Min heap
*/
public class TernaryMinHeap
{
// 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
};
// Get the number of elements
int size = node.Length;
// Construct Min heap
/*
Min heap
-----------------------
1
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
4         2         9
/ |  \    / | \
7  10  6  3  8  5
----------------------------
Constructed Tree
*/
Console.Write(" Preorder\n");
}
}``````

#### Output

`````` Preorder
1  4  7  10  6  2  3  8  5  9``````
``````<?php
/*
Php program
Implement Ternary Min heap
*/
class TernaryMinHeap
{
// 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);
// Get the number of elements
\$size = count(\$node);
// Construct Min heap
/*
Min heap
-----------------------
1
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
4         2         9
/ |  \    / | \
7  10  6  3  8  5
----------------------------
Constructed Tree
*/
echo " Preorder\n";
}
main();``````

#### Output

`````` Preorder
1  4  7  10  6  2  3  8  5  9``````
``````/*
Node Js program
Implement Ternary Min heap
*/
class TernaryMinHeap
{
// 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];
// Get the number of elements
var size = node.length;
// Construct Min heap
/*
Min heap
-----------------------
1
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
4         2         9
/ |  \    / | \
7  10  6  3  8  5
----------------------------
Constructed Tree
*/
process.stdout.write(" Preorder\n");
}
main();``````

#### Output

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

class TernaryMinHeap :
#  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]
#  Get the number of elements
size = len(node)
#  Construct Min heap
#
# Min heap
# -----------------------
#               1
#             / | \
#            /  |  \
#           /   |   \
#          /    |    \
#         /     |     \
#        /      |      \
#       /       |       \
#      /        |        \
#     4         2         9
#   / |  \    / | \
#  7  10  6  3  8  5
# ----------------------------
#         Constructed Tree

print(" Preorder")

if __name__ == "__main__": main()``````

#### Output

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

class TernaryMinHeap
#  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]
#  Get the number of elements
size = node.length
#  Construct Min heap
#
# Min heap
# -----------------------
#               1
#             / | \
#            /  |  \
#           /   |   \
#          /    |    \
#         /     |     \
#        /      |      \
#       /       |       \
#      /        |        \
#     4         2         9
#   / |  \    / | \
#  7  10  6  3  8  5
# ----------------------------
#         Constructed Tree

print(" Preorder\n")
end

main()``````

#### Output

`````` Preorder
1  4  7  10  6  2  3  8  5  9``````
``````/*
Scala program
Implement Ternary Min heap
*/
class TernaryMinHeap
{
// 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: TernaryMinHeap = new TernaryMinHeap();
// Tree nodes
var node: Array[Int] = Array(10, 7, 2, 9, 1, 4, 6, 3, 8, 5);
// Get the number of elements
var size: Int = node.length;
// Construct Min heap
/*
Min heap
-----------------------
1
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
4         2         9
/ |  \    / | \
7  10  6  3  8  5
----------------------------
Constructed Tree
*/
print(" Preorder\n");
}
}``````

#### Output

`````` Preorder
1  4  7  10  6  2  3  8  5  9``````
``````/*
Swift 4 program
Implement Ternary Min heap
*/
class TernaryMinHeap
{
// 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];
// Get the number of elements
let size: Int = node.count;
// Construct Min heap
/*
Min heap
-----------------------
1
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
4         2         9
/ |  \    / | \
7  10  6  3  8  5
----------------------------
Constructed Tree
*/
print(" Preorder");
}
main();``````

#### Output

`````` Preorder
1   4   7   10   6   2   3   8   5   9``````
``````/*
Kotlin program
Implement Ternary Min heap
*/
class TernaryMinHeap
{
// 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);
// Get the number of elements
var size: Int = node.count();
// Construct Min heap
/*
Min heap
-----------------------
1
/ | \
/  |  \
/   |   \
/    |    \
/     |     \
/      |      \
/       |       \
/        |        \
4         2         9
/ |  \    / | \
7  10  6  3  8  5
----------------------------
Constructed Tree
*/
print(" Preorder\n");
}``````

#### Output

`````` Preorder
1  4  7  10  6  2  3  8  5  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.

Categories
Relative Post