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);
if (task != -1)
{
// Recursively execute function, when tasks are remain
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--)
{
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[0]);
// 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);
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)
{
TernaryMinHeap task = new TernaryMinHeap();
// 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
task.makeTernaryHeap(node, size);
/*Min heap
-----------------------
1
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
4 2 9
/ | \ / | \
7 10 6 3 8 5
----------------------------
Constructed Tree
*/
System.out.print(" Preorder\n");
task.preorder(node, size, 0);
}
}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);
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()
{
TernaryMinHeap task = TernaryMinHeap();
// 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[0]);
// Construct Min heap
task.makeTernaryHeap(node, size);
/*
Min heap
-----------------------
1
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
4 2 9
/ | \ / | \
7 10 6 3 8 5
----------------------------
Constructed Tree
*/
cout << " Preorder\n";
task.preorder(node, size, 0);
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);
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)
{
TernaryMinHeap task = new TernaryMinHeap();
// 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
task.makeTernaryHeap(node, size);
/*
Min heap
-----------------------
1
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
4 2 9
/ | \ / | \
7 10 6 3 8 5
----------------------------
Constructed Tree
*/
Console.Write(" Preorder\n");
task.preorder(node, size, 0);
}
}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)
{
$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 TernaryMinHeap();
// 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
$task->makeTernaryHeap($node, $size);
/*
Min heap
-----------------------
1
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
4 2 9
/ | \ / | \
7 10 6 3 8 5
----------------------------
Constructed Tree
*/
echo " Preorder\n";
$task->preorder($node, $size, 0);
}
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);
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 TernaryMinHeap();
// 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
task.makeTernaryHeap(node, size);
/*
Min heap
-----------------------
1
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
4 2 9
/ | \ / | \
7 10 6 3 8 5
----------------------------
Constructed Tree
*/
process.stdout.write(" Preorder\n");
task.preorder(node, size, 0);
}
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) :
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 = TernaryMinHeap()
# Tree nodes
node = [10, 7, 2, 9, 1, 4, 6, 3, 8, 5]
# Get the number of elements
size = len(node)
# Construct Min heap
task.makeTernaryHeap(node, size)
#
# Min heap
# -----------------------
# 1
# / | \
# / | \
# / | \
# / | \
# / | \
# / | \
# / | \
# / | \
# 4 2 9
# / | \ / | \
# 7 10 6 3 8 5
# ----------------------------
# Constructed Tree
print(" Preorder")
task.preorder(node, size, 0)
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)
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 = TernaryMinHeap.new()
# Tree nodes
node = [10, 7, 2, 9, 1, 4, 6, 3, 8, 5]
# Get the number of elements
size = node.length
# Construct Min heap
task.makeTernaryHeap(node, size)
#
# Min heap
# -----------------------
# 1
# / | \
# / | \
# / | \
# / | \
# / | \
# / | \
# / | \
# / | \
# 4 2 9
# / | \ / | \
# 7 10 6 3 8 5
# ----------------------------
# Constructed Tree
print(" Preorder\n")
task.preorder(node, size, 0)
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);
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: 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
task.makeTernaryHeap(node, size);
/*
Min heap
-----------------------
1
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
4 2 9
/ | \ / | \
7 10 6 3 8 5
----------------------------
Constructed Tree
*/
print(" Preorder\n");
task.preorder(node, size, 0);
}
}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);
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: TernaryMinHeap = TernaryMinHeap();
// 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
task.makeTernaryHeap(&node, size);
/*
Min heap
-----------------------
1
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
4 2 9
/ | \ / | \
7 10 6 3 8 5
----------------------------
Constructed Tree
*/
print(" Preorder");
task.preorder(node, size, 0);
}
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);
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: TernaryMinHeap = TernaryMinHeap();
// 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
task.makeTernaryHeap(node, size);
/*
Min heap
-----------------------
1
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
4 2 9
/ | \ / | \
7 10 6 3 8 5
----------------------------
Constructed Tree
*/
print(" Preorder\n");
task.preorder(node, size, 0);
}Output
Preorder
1 4 7 10 6 2 3 8 5 9
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