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:

Ternary Min heap

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

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