Posted on by Kalkicode
Code Heap

K-ary Heap

A k-ary heap is a tree-based data structure, which is similar to a binary heap, but instead of having each node have at most two children, each node in a k-ary heap has at most k children.

In a k-ary heap, the first element of the array represents the root of the heap, and the subsequent elements represent the nodes in level-order traversal. Each node in the heap has a value, and the heap property is maintained such that the value of each node is greater than or equal to the values of its children (if any).

K-ary heaps are used to implement priority queues, and they have a time complexity of O(log n) for inserting or deleting an element from the heap, and O(1) for finding the maximum or minimum element in the heap. The value of k can affect the efficiency of the heap operations, with larger values of k generally resulting in faster insertion and deletion but slower finding of the maximum or minimum element.

Here given code implementation process.

/*
  C Program 
  K-ary Heap
*/

#include <stdio.h>
#include <stdlib.h>

struct KAryHeap
{
    int limit; // Number of element
    int n; // Current element
    int k ; // Number of child
    int *collection;
};

// Returns a new heap
struct KAryHeap* newHeap(int limit, int k)
{
    struct KAryHeap* heap = (struct KAryHeap*)malloc(sizeof(struct KAryHeap));
    if(heap==NULL)
    {
        printf("\n Memory Overflow, when creating new heap\n");
        return NULL;
    }
    // Set How many number of elements possible in heap
    heap->limit = limit;

    // Set intial no element in heap
    heap->n = 0;

    // Set number of child nodes
    heap->k = k;

    // Allocate memory of heap elements
    heap->collection = (int *)calloc(limit,sizeof(int));

    if(heap->collection == NULL)
    {
        printf("\n Memory Overflow, when creating new heap collection\n");
    }

    return heap;
}

// Display pre order view of ternary tree
void preorder(struct KAryHeap*heap, int root)
{
    if ( root < heap->n)
    {
        printf("  %d", heap->collection[root]);
        // Recursive visit to child node
        for (int i = 1; i <= heap->k; ++i)
        {
            preorder(heap,heap->k *root + i);
        }
    }
}


// Swap two elements of heap collection
void swap(struct KAryHeap*heap, int first, int second)
{
    int auxiliary = heap->collection[first];
    heap->collection[first] = heap->collection[second];
    heap->collection[second] = auxiliary;
}

// This are converting tree into valid max heap when insert new element
void putElement(struct KAryHeap*heap, int location) 
{ 
    int root = (location-1)/heap->k; 
  
    while (root >= 0 && heap->collection[location] > heap->collection[root]) 
    { 
        swap(heap, location, root); 
        location = root; 
        root = (location-1)/heap->k; 
    } 
} 
// Handles the request of adding  new heap element
void addElement(struct KAryHeap*heap, int data)
{
    if(heap->n+1 >= heap->limit)
    {
        printf("\n Heap limit is exceeded When add new element");
        return;
    }
    heap->collection[heap->n] = data;
    heap->n = heap->n + 1;
    putElement(heap, heap->n-1);  
}




// After remove top of tree this are converted into a new max heap
void changeElement(struct KAryHeap*heap, int location)
{
    int update = -1;
    for (int i = 1; i <= heap->k; ++i)
    {
        if((location*heap->k)+i < heap->n && heap->collection[location] < 
            heap->collection[(location*heap->k)+i])

        {
            if(update == -1)
            {
                // First largest child
                update = (location*heap->k)+i;
            }
            else if(heap->collection[update] < heap->collection[(location*heap->k)+i])
            {
                // When previous child is smaller
                update = (location*heap->k)+i;
            }
        }
    }

    if(update >= 0)
    {
        // Swap element
        swap(heap,location,update);
        // Check next updation
        changeElement(heap,update);
    }
}
// Remove the max element from the tree
int extractMax(struct KAryHeap*heap) 
{
    if(heap->n == 0)
    {
        printf("\n Empty Heap ");
        return -1;
    }
    int element = heap->collection[0];

    heap->collection[0] = heap->collection[heap->n-1];

    heap->collection[heap->n-1] = 0;

    heap->n = heap->n - 1;

    changeElement(heap, 0); 

    return element;
}

// Handles the request of displaying Tree elements
void printTree(struct KAryHeap*heap)
{   
    printf("\n Level Order Heap Element  \n"); 
   
    for (int i=0; i < heap->n; i++) 
    {
        printf("  %d", heap->collection[i]); 
    }
    printf("\n Preorder \n");
    preorder(heap,0);
}

int main()
{

    // Number of elements in heap
    // Set limit
    int limit = 50; 
    // Possible child
    int k = 4;

    struct KAryHeap*heap = newHeap(limit,k);

    // Add heap element
    addElement(heap,10);
    addElement(heap,7);
    addElement(heap,40);
    addElement(heap,2);
    addElement(heap,5);
    addElement(heap,15);
    addElement(heap,21);
    addElement(heap,35);
    addElement(heap,49);
    addElement(heap,38);
    addElement(heap,63);
    addElement(heap,19);

    /* Max heap of K 4
    -----------------------   
    

                       63
        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
        │               │       │    │ 
        40              49      2    5
        |               │
    ┌‒‒‒┬‒‒‒┬‒‒‒┐   ┌‒‒‒┬‒‒‒┐
    │   │   │   │   │   │   │    
    7  15   21  35  10  38  19
    -------------------------------
            Constructed Tree               
    */
    printTree(heap);

    printf("\n Extract Max Element : %d",extractMax(heap));

    /*  Extract Max Element
    -----------------------   
    

                       (49)
        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
        │               │       │    │ 
      (40)             (38)     2    5
        |               │
    ┌‒‒‒┬‒‒‒┬‒‒‒┐     ┌‒‒‒┐
    │   │   │   │     │   │      
    7  15   21  35    10  19  
    -------------------------------
            After remove max node              
    */
    printTree(heap);
    return 0;
}

Output

 Level Order Heap Element
  63  40  49  2  5  7  15  21  35  10  38  19
 Preorder
  63  40  7  15  21  35  49  10  38  19  2  5
 Extract Max Element : 63
 Level Order Heap Element
  49  40  38  2  5  7  15  21  35  10  19
 Preorder
  49  40  7  15  21  35  38  10  19  2  5
/*
    Java program
    K-ary Heap
*/
public class KAryHeap
{
	public int limit;
	// Number of element
	public int n;
	// Current element
	public int k;
	// Number of child
	public int[] collection;
	public KAryHeap(int limit, int k)
	{
		// Set How many number of elements possible in heap
		this.limit = limit;
		// Set intial no element in heap
		this.n = 0;
		// Set number of child nodes
		this.k = k;
		// Allocate memory of heap elements
		this.collection = new int[limit];
	}
	// Display pre order view of ternary tree
	public void preorder(int root)
	{
		if (root < this.n)
		{
			System.out.print("  " + this.collection[root]);
			// Recursive visit to child node
			for (int i = 1; i <= this.k; ++i)
			{
				preorder(this.k * root + i);
			}
		}
	}
	// Swap two elements of heap collection
	public void swap(int first, int second)
	{
		int auxiliary = this.collection[first];
		this.collection[first] = this.collection[second];
		this.collection[second] = auxiliary;
	}
	// This are converting tree into valid max heap when insert new element
	public void putElement(int location)
	{
		int root = (location - 1) / this.k;
		while (root >= 0 && this.collection[location] > this.collection[root])
		{
			swap(location, root);
			location = root;
			root = (location - 1) / this.k;
		}
	}
	// Handles the request of adding  new heap element
	public void addElement(int data)
	{
		if (this.n + 1 >= this.limit)
		{
			System.out.print("\n Heap limit is exceeded When add new element");
			return;
		}
		this.collection[this.n] = data;
		this.n = this.n + 1;
		putElement(this.n - 1);
	}
	// After remove top of tree this are converted into a new max heap
	public void changeElement(int location)
	{
		int update = -1;
		for (int i = 1; i <= this.k; ++i)
		{
			if ((location * this.k) + i < this.n && this.collection[location] < this.collection[(location * this.k) + i])
			{
				if (update == -1)
				{
					// First largest child
					update = (location * this.k) + i;
				}
				else if (this.collection[update] < this.collection[(location * this.k) + i])
				{
					// When previous child is smaller
					update = (location * this.k) + i;
				}
			}
		}
		if (update >= 0)
		{
			// Swap element
			swap(location, update);
			// Check next updation
			changeElement(update);
		}
	}
	// Remove the max element from the tree
	public int extractMax()
	{
		if (this.n == 0)
		{
			System.out.print("\n Empty Heap ");
			return -1;
		}
		int element = this.collection[0];
		this.collection[0] = this.collection[this.n - 1];
		this.collection[this.n - 1] = 0;
		this.n = this.n - 1;
		changeElement(0);
		return element;
	}
	// Handles the request of displaying Tree elements
	public void printTree()
	{
		System.out.print("\n Level Order Heap Element \n");
		for (int i = 0; i < this.n; i++)
		{
			System.out.print("  " + this.collection[i]);
		}
		System.out.print("\n Preorder \n");
		preorder(0);
	}
	public static void main(String[] args)
	{
		// Number of elements in heap
		// Set limit
		int limit = 50;
		// Possible child
		int k = 4;
		KAryHeap heap = new KAryHeap(limit, k);
		// Add heap element
		heap.addElement(10);
		heap.addElement(7);
		heap.addElement(40);
		heap.addElement(2);
		heap.addElement(5);
		heap.addElement(15);
		heap.addElement(21);
		heap.addElement(35);
		heap.addElement(49);
		heap.addElement(38);
		heap.addElement(63);
		heap.addElement(19);
		/*Max heap of K 4
		        -----------------------   
		        
		                       63
		        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
		        │               │       │    │ 
		        40              49      2    5
		        |               │
		    ┌‒‒‒┬‒‒‒┬‒‒‒┐   ┌‒‒‒┬‒‒‒┐
		    │   │   │   │   │   │   │    
		    7  15   21  35  10  38  19
		    -------------------------------
		            Constructed Tree               
		        
		*/
		heap.printTree();
		System.out.print("\n Extract Max Element : " + heap.extractMax());
		/* Extract Max Element
		  -----------------------   
		    
		                       (49)
		        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
		        │               │       │    │ 
		      (40)             (38)     2    5
		        |               │
		    ┌‒‒‒┬‒‒‒┬‒‒‒┐     ┌‒‒‒┐
		    │   │   │   │     │   │      
		    7  15   21  35    10  19  
		    -------------------------------
		            After remove max node              
		        
		*/
		heap.printTree();
	}
}

Output

 Level Order Heap Element
  63  40  49  2  5  7  15  21  35  10  38  19
 Preorder
  63  40  7  15  21  35  49  10  38  19  2  5
 Extract Max Element : 63
 Level Order Heap Element
  49  40  38  2  5  7  15  21  35  10  19
 Preorder
  49  40  7  15  21  35  38  10  19  2  5
// Include header file
#include <iostream>

using namespace std;
/*
    C++ program
    K-ary Heap
*/
class KAryHeap
{
	public: int limit;
	// Number of element
	int n;
	// Current element
	int k;
	// Number of child
	int *collection;
	KAryHeap(int limit, int k)
	{
		// Set How many number of elements possible in heap
		this->limit = limit;
		// Set intial no element in heap
		this->n = 0;
		// Set number of child nodes
		this->k = k;
		// Allocate memory of heap elements
		this->collection = new int[limit];
	}
	// Display pre order view of ternary tree
	void preorder(int root)
	{
		if (root < this->n)
		{
			cout << "  " << this->collection[root];
			// Recursive visit to child node
			for (int i = 1; i <= this->k; ++i)
			{
				this->preorder(this->k *root + i);
			}
		}
	}
	// Swap two elements of heap collection
	void swap(int first, int second)
	{
		int auxiliary = this->collection[first];
		this->collection[first] = this->collection[second];
		this->collection[second] = auxiliary;
	}
	// This are converting tree into valid max heap when insert new element
	void putElement(int location)
	{
		int root = (location - 1) / this->k;
		while (root >= 0 && this->collection[location] > this->collection[root])
		{
			this->swap(location, root);
			location = root;
			root = (location - 1) / this->k;
		}
	}
	// Handles the request of adding  new heap element
	void addElement(int data)
	{
		if (this->n + 1 >= this->limit)
		{
			cout << "\n Heap limit is exceeded When add new element";
			return;
		}
		this->collection[this->n] = data;
		this->n = this->n + 1;
		this->putElement(this->n - 1);
	}
	// After remove top of tree this are converted into a new max heap
	void changeElement(int location)
	{
		int update = -1;
		for (int i = 1; i <= this->k; ++i)
		{
			if ((location *this->k) + i < this->n && this->collection[location] < this->collection[(location *this->k) + i])
			{
				if (update == -1)
				{
					// First largest child
					update = (location *this->k) + i;
				}
				else if (this->collection[update] < this->collection[(location *this->k) + i])
				{
					// When previous child is smaller
					update = (location *this->k) + i;
				}
			}
		}
		if (update >= 0)
		{
			// Swap element
			this->swap(location, update);
			// Check next updation
			this->changeElement(update);
		}
	}
	// Remove the max element from the tree
	int extractMax()
	{
		if (this->n == 0)
		{
			cout << "\n Empty Heap ";
			return -1;
		}
		int element = this->collection[0];
		this->collection[0] = this->collection[this->n - 1];
		this->collection[this->n - 1] = 0;
		this->n = this->n - 1;
		this->changeElement(0);
		return element;
	}
	// Handles the request of displaying Tree elements
	void printTree()
	{
		cout << "\n Level Order Heap Element \n";
		for (int i = 0; i < this->n; i++)
		{
			cout << "  " << this->collection[i];
		}
		cout << "\n Preorder \n";
		this->preorder(0);
	}
};
int main()
{
	// Number of elements in heap
	// Set limit
	int limit = 50;
	// Possible child
	int k = 4;
	KAryHeap heap = KAryHeap(limit, k);
	// Add heap element
	heap.addElement(10);
	heap.addElement(7);
	heap.addElement(40);
	heap.addElement(2);
	heap.addElement(5);
	heap.addElement(15);
	heap.addElement(21);
	heap.addElement(35);
	heap.addElement(49);
	heap.addElement(38);
	heap.addElement(63);
	heap.addElement(19);
	/*Max heap of K 4
	        -----------------------   
	        
	                       63
	        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	        │               │       │    │ 
	        40              49      2    5
	        |               │
	    ┌‒‒‒┬‒‒‒┬‒‒‒┐   ┌‒‒‒┬‒‒‒┐
	    │   │   │   │   │   │   │    
	    7  15   21  35  10  38  19
	    -------------------------------
	            Constructed Tree               
	        
	*/
	heap.printTree();
	cout << "\n Extract Max Element : " << heap.extractMax();
	/*Extract Max Element
	  -----------------------   
	    
	                       (49)
	        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	        │               │       │    │ 
	      (40)             (38)     2    5
	        |               │
	    ┌‒‒‒┬‒‒‒┬‒‒‒┐     ┌‒‒‒┐
	    │   │   │   │     │   │      
	    7  15   21  35    10  19  
	    -------------------------------
	            After remove max node              
	        
	*/
	heap.printTree();
	return 0;
}

Output

 Level Order Heap Element
  63  40  49  2  5  7  15  21  35  10  38  19
 Preorder
  63  40  7  15  21  35  49  10  38  19  2  5
 Extract Max Element : 63
 Level Order Heap Element
  49  40  38  2  5  7  15  21  35  10  19
 Preorder
  49  40  7  15  21  35  38  10  19  2  5
// Include namespace system
using System;
/*
    C# program
    K-ary Heap
*/
public class KAryHeap
{
	public int limit;
	// Number of element
	public int n;
	// Current element
	public int k;
	// Number of child
	public int[] collection;
	public KAryHeap(int limit, int k)
	{
		// Set How many number of elements possible in heap
		this.limit = limit;
		// Set intial no element in heap
		this.n = 0;
		// Set number of child nodes
		this.k = k;
		// Allocate memory of heap elements
		this.collection = new int[limit];
	}
	// Display pre order view of ternary tree
	public void preorder(int root)
	{
		if (root < this.n)
		{
			Console.Write("  " + this.collection[root]);
			// Recursive visit to child node
			for (int i = 1; i <= this.k; ++i)
			{
				preorder(this.k * root + i);
			}
		}
	}
	// Swap two elements of heap collection
	public void swap(int first, int second)
	{
		int auxiliary = this.collection[first];
		this.collection[first] = this.collection[second];
		this.collection[second] = auxiliary;
	}
	// This are converting tree into valid max heap when insert new element
	public void putElement(int location)
	{
		int root = (location - 1) / this.k;
		while (root >= 0 && this.collection[location] > this.collection[root])
		{
			swap(location, root);
			location = root;
			root = (location - 1) / this.k;
		}
	}
	// Handles the request of adding  new heap element
	public void addElement(int data)
	{
		if (this.n + 1 >= this.limit)
		{
			Console.Write("\n Heap limit is exceeded When add new element");
			return;
		}
		this.collection[this.n] = data;
		this.n = this.n + 1;
		putElement(this.n - 1);
	}
	// After remove top of tree this are converted into a new max heap
	public void changeElement(int location)
	{
		int update = -1;
		for (int i = 1; i <= this.k; ++i)
		{
			if ((location * this.k) + i < this.n && this.collection[location] < this.collection[(location * this.k) + i])
			{
				if (update == -1)
				{
					// First largest child
					update = (location * this.k) + i;
				}
				else if (this.collection[update] < this.collection[(location * this.k) + i])
				{
					// When previous child is smaller
					update = (location * this.k) + i;
				}
			}
		}
		if (update >= 0)
		{
			// Swap element
			swap(location, update);
			// Check next updation
			changeElement(update);
		}
	}
	// Remove the max element from the tree
	public int extractMax()
	{
		if (this.n == 0)
		{
			Console.Write("\n Empty Heap ");
			return -1;
		}
		int element = this.collection[0];
		this.collection[0] = this.collection[this.n - 1];
		this.collection[this.n - 1] = 0;
		this.n = this.n - 1;
		changeElement(0);
		return element;
	}
	// Handles the request of displaying Tree elements
	public void printTree()
	{
		Console.Write("\n Level Order Heap Element \n");
		for (int i = 0; i < this.n; i++)
		{
			Console.Write("  " + this.collection[i]);
		}
		Console.Write("\n Preorder \n");
		preorder(0);
	}
	public static void Main(String[] args)
	{
		// Number of elements in heap
		// Set limit
		int limit = 50;
		// Possible child
		int k = 4;
		KAryHeap heap = new KAryHeap(limit, k);
		// Add heap element
		heap.addElement(10);
		heap.addElement(7);
		heap.addElement(40);
		heap.addElement(2);
		heap.addElement(5);
		heap.addElement(15);
		heap.addElement(21);
		heap.addElement(35);
		heap.addElement(49);
		heap.addElement(38);
		heap.addElement(63);
		heap.addElement(19);
		/*Max heap of K 4
		        -----------------------   
		        
		                       63
		        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
		        │               │       │    │ 
		        40              49      2    5
		        |               │
		    ┌‒‒‒┬‒‒‒┬‒‒‒┐   ┌‒‒‒┬‒‒‒┐
		    │   │   │   │   │   │   │    
		    7  15   21  35  10  38  19
		    -------------------------------
		            Constructed Tree               
		        
		*/
		heap.printTree();
		Console.Write("\n Extract Max Element : " + heap.extractMax());
		/* Extract Max Element
		  -----------------------   
		    
		                       (49)
		        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
		        │               │       │    │ 
		      (40)             (38)     2    5
		        |               │
		    ┌‒‒‒┬‒‒‒┬‒‒‒┐     ┌‒‒‒┐
		    │   │   │   │     │   │      
		    7  15   21  35    10  19  
		    -------------------------------
		            After remove max node              
		        
		*/
		heap.printTree();
	}
}

Output

 Level Order Heap Element
  63  40  49  2  5  7  15  21  35  10  38  19
 Preorder
  63  40  7  15  21  35  49  10  38  19  2  5
 Extract Max Element : 63
 Level Order Heap Element
  49  40  38  2  5  7  15  21  35  10  19
 Preorder
  49  40  7  15  21  35  38  10  19  2  5
<?php
/*
    Php program
    K-ary Heap
*/
class KAryHeap
{
	public $limit;
	// Number of element
	public $n;
	// Current element
	public $k;
	// Number of child
	public $collection;

	function __construct($limit, $k)
	{
		// Set How many number of elements possible in heap
		$this->limit = $limit;
		// Set intial no element in heap
		$this->n = 0;
		// Set number of child nodes
		$this->k = $k;
		// Allocate memory of heap elements
		$this->collection = array_fill(0, $limit, 0);
	}
	// Display pre order view of ternary tree
	public	function preorder($root)
	{
		if ($root < $this->n)
		{
			echo "  ". $this->collection[$root];
			// Recursive visit to child node
			for ($i = 1; $i <= $this->k; ++$i)
			{
				$this->preorder($this->k * $root + $i);
			}
		}
	}
	// Swap two elements of heap collection
	public	function swap($first, $second)
	{
		$auxiliary = $this->collection[$first];
		$this->collection[$first] = $this->collection[$second];
		$this->collection[$second] = $auxiliary;
	}
	// This are converting tree into valid max heap when insert new element
	public	function putElement($location)
	{
		$root = intval(($location - 1) / $this->k);
		while ($root >= 0 && $this->collection[$location] > $this->collection[$root])
		{
			$this->swap($location, $root);
			$location = $root;
			$root = intval(($location - 1) / $this->k);
		}
	}
	// Handles the request of adding  new heap element
	public	function addElement($data)
	{
		if ($this->n + 1 >= $this->limit)
		{
			echo "\n Heap limit is exceeded When add new element";
			return;
		}
		$this->collection[$this->n] = $data;
		$this->n = $this->n + 1;
		$this->putElement($this->n - 1);
	}
	// After remove top of tree this are converted into a new max heap
	public	function changeElement($location)
	{
		$update = -1;
		for ($i = 1; $i <= $this->k; ++$i)
		{
			if (($location * $this->k) + $i < $this->n && $this->collection[$location] < $this->collection[($location * $this->k) + $i])
			{
				if ($update == -1)
				{
					// First largest child
					$update = ($location * $this->k) + $i;
				}
				else if ($this->collection[$update] < $this->collection[($location * $this->k) + $i])
				{
					// When previous child is smaller
					$update = ($location * $this->k) + $i;
				}
			}
		}
		if ($update >= 0)
		{
			// Swap element
			$this->swap($location, $update);
			// Check next updation
			$this->changeElement($update);
		}
	}
	// Remove the max element from the tree
	public	function extractMax()
	{
		if ($this->n == 0)
		{
			echo "\n Empty Heap ";
			return -1;
		}
		$element = $this->collection[0];
		$this->collection[0] = $this->collection[$this->n - 1];
		$this->collection[$this->n - 1] = 0;
		$this->n = $this->n - 1;
		$this->changeElement(0);
		return $element;
	}
	// Handles the request of displaying Tree elements
	public	function printTree()
	{
		echo "\n Level Order Heap Element \n";
		for ($i = 0; $i < $this->n; $i++)
		{
			echo "  ". $this->collection[$i];
		}
		echo "\n Preorder \n";
		$this->preorder(0);
	}
}

function main()
{
	// Number of elements in heap
	// Set limit
	$limit = 50;
	// Possible child
	$k = 4;
	$heap = new KAryHeap($limit, $k);
	// Add heap element
	$heap->addElement(10);
	$heap->addElement(7);
	$heap->addElement(40);
	$heap->addElement(2);
	$heap->addElement(5);
	$heap->addElement(15);
	$heap->addElement(21);
	$heap->addElement(35);
	$heap->addElement(49);
	$heap->addElement(38);
	$heap->addElement(63);
	$heap->addElement(19);
	/*Max heap of K 4
	        -----------------------   
	        
	                       63
	        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	        │               │       │    │ 
	        40              49      2    5
	        |               │
	    ┌‒‒‒┬‒‒‒┬‒‒‒┐   ┌‒‒‒┬‒‒‒┐
	    │   │   │   │   │   │   │    
	    7  15   21  35  10  38  19
	    -------------------------------
	            Constructed Tree               
	        
	*/
	$heap->printTree();
	echo "\n Extract Max Element : ". $heap->extractMax();
	/* Extract Max Element
	  -----------------------   
	    
	                       (49)
	        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	        │               │       │    │ 
	      (40)             (38)     2    5
	        |               │
	    ┌‒‒‒┬‒‒‒┬‒‒‒┐     ┌‒‒‒┐
	    │   │   │   │     │   │      
	    7  15   21  35    10  19  
	    -------------------------------
	            After remove max node              
	        
	*/
	$heap->printTree();
}
main();

Output

 Level Order Heap Element
  63  40  49  2  5  7  15  21  35  10  38  19
 Preorder
  63  40  7  15  21  35  49  10  38  19  2  5
 Extract Max Element : 63
 Level Order Heap Element
  49  40  38  2  5  7  15  21  35  10  19
 Preorder
  49  40  7  15  21  35  38  10  19  2  5
/*
    Node Js program
    K-ary Heap
*/
class KAryHeap
{
	// Number of element
	// Current element
	// Number of child
	constructor(limit, k)
	{
		// Set How many number of elements possible in heap
		this.limit = limit;
		// Set intial no element in heap
		this.n = 0;
		// Set number of child nodes
		this.k = k;
		// Allocate memory of heap elements
		this.collection = Array(limit).fill(0);
	}
	// Display pre order view of ternary tree
	preorder(root)
	{
		if (root < this.n)
		{
			process.stdout.write("  " + this.collection[root]);
			// Recursive visit to child node
			for (var i = 1; i <= this.k; ++i)
			{
				this.preorder(this.k * root + i);
			}
		}
	}
	// Swap two elements of heap collection
	swap(first, second)
	{
		var auxiliary = this.collection[first];
		this.collection[first] = this.collection[second];
		this.collection[second] = auxiliary;
	}
	// This are converting tree into valid max heap when insert new element
	putElement(location)
	{
		var root = parseInt((location - 1) / this.k);
		while (root >= 0 && this.collection[location] > this.collection[root])
		{
			this.swap(location, root);
			location = root;
			root = parseInt((location - 1) / this.k);
		}
	}
	// Handles the request of adding  new heap element
	addElement(data)
	{
		if (this.n + 1 >= this.limit)
		{
			process.stdout.write("\n Heap limit is exceeded When add new element");
			return;
		}
		this.collection[this.n] = data;
		this.n = this.n + 1;
		this.putElement(this.n - 1);
	}
	// After remove top of tree this are converted into a new max heap
	changeElement(location)
	{
		var update = -1;
		for (var i = 1; i <= this.k; ++i)
		{
			if ((location * this.k) + i < this.n 
                && this.collection[location] < this.collection[(location * this.k) + i])
			{
				if (update == -1)
				{
					// First largest child
					update = (location * this.k) + i;
				}
				else if (this.collection[update] < this.collection[(location * this.k) + i])
				{
					// When previous child is smaller
					update = (location * this.k) + i;
				}
			}
		}
		if (update >= 0)
		{
			// Swap element
			this.swap(location, update);
			// Check next updation
			this.changeElement(update);
		}
	}
	// Remove the max element from the tree
	extractMax()
	{
		if (this.n == 0)
		{
			process.stdout.write("\n Empty Heap ");
			return -1;
		}
		var element = this.collection[0];
		this.collection[0] = this.collection[this.n - 1];
		this.collection[this.n - 1] = 0;
		this.n = this.n - 1;
		this.changeElement(0);
		return element;
	}
	// Handles the request of displaying Tree elements
	printTree()
	{
		process.stdout.write("\n Level Order Heap Element \n");
		for (var i = 0; i < this.n; i++)
		{
			process.stdout.write("  " + this.collection[i]);
		}
		process.stdout.write("\n Preorder \n");
		this.preorder(0);
	}
}

function main()
{
	// Number of elements in heap
	// Set limit
	var limit = 50;
	// Possible child
	var k = 4;
	var heap = new KAryHeap(limit, k);
	// Add heap element
	heap.addElement(10);
	heap.addElement(7);
	heap.addElement(40);
	heap.addElement(2);
	heap.addElement(5);
	heap.addElement(15);
	heap.addElement(21);
	heap.addElement(35);
	heap.addElement(49);
	heap.addElement(38);
	heap.addElement(63);
	heap.addElement(19);
	/*Max heap of K 4
	        -----------------------   
	        
	                       63
	        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	        │               │       │    │ 
	        40              49      2    5
	        |               │
	    ┌‒‒‒┬‒‒‒┬‒‒‒┐   ┌‒‒‒┬‒‒‒┐
	    │   │   │   │   │   │   │    
	    7  15   21  35  10  38  19
	    -------------------------------
	            Constructed Tree               
	        
	*/
	heap.printTree();
	process.stdout.write("\n Extract Max Element : " + heap.extractMax());
	/* Extract Max Element
	  -----------------------   
	    
	                       (49)
	        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	        │               │       │    │ 
	      (40)             (38)     2    5
	        |               │
	    ┌‒‒‒┬‒‒‒┬‒‒‒┐     ┌‒‒‒┐
	    │   │   │   │     │   │      
	    7  15   21  35    10  19  
	    -------------------------------
	            After remove max node              
	        
	*/
	heap.printTree();
}
main();

Output

 Level Order Heap Element
  63  40  49  2  5  7  15  21  35  10  38  19
 Preorder
  63  40  7  15  21  35  49  10  38  19  2  5
 Extract Max Element : 63
 Level Order Heap Element
  49  40  38  2  5  7  15  21  35  10  19
 Preorder
  49  40  7  15  21  35  38  10  19  2  5
#  Python 3 program
#  K-ary Heap

class KAryHeap :

	
	def __init__(self, limit, k) :
		#  Set How many number of elements possible in heap
		self.limit = limit
		#  Set intial no element in heap
		self.n = 0
		#  Set number of child nodes
		self.k = k
		#  Allocate memory of heap elements
		self.collection = [0] * (limit)
	
	#  Display pre order view of ternary tree
	def preorder(self, root) :
		if (root < self.n) :
			print("  ", self.collection[root], end = "")
			i = 1
			#  Recursive visit to child node
			while (i <= self.k) :
				self.preorder(self.k * root + i)
				i += 1
			
		
	
	#  Swap two elements of heap collection
	def swap(self, first, second) :
		auxiliary = self.collection[first]
		self.collection[first] = self.collection[second]
		self.collection[second] = auxiliary
	
	#  This are converting tree into valid max heap when insert new element
	def putElement(self, location) :
		root = int((location - 1) / self.k)
		while (root >= 0 and self.collection[location] > self.collection[root]) :
			self.swap(location, root)
			location = root
			root = int((location - 1) / self.k)
		
	
	#  Handles the request of adding  new heap element
	def addElement(self, data) :
		if (self.n + 1 >= self.limit) :
			print("\n Heap limit is exceeded When add new element", end = "")
			return
		
		self.collection[self.n] = data
		self.n = self.n + 1
		self.putElement(self.n - 1)
	
	#  After remove top of tree this are converted into a new max heap
	def changeElement(self, location) :
		update = -1
		i = 1
		while (i <= self.k) :
			if ((location * self.k) + i < self.n 
                and self.collection[location] < self.collection[(location * self.k) + i]) :
				if (update == -1) :
					#  First largest child
					update = (location * self.k) + i
				
				elif(self.collection[update] < self.collection[(location * self.k) + i]) :
					#  When previous child is smaller
					update = (location * self.k) + i
				
			
			i += 1
		
		if (update >= 0) :
			#  Swap element
			self.swap(location, update)
			#  Check next updation
			self.changeElement(update)
		
	
	#  Remove the max element from the tree
	def extractMax(self) :
		if (self.n == 0) :
			print("\n Empty Heap ", end = "")
			return -1
		
		element = self.collection[0]
		self.collection[0] = self.collection[self.n - 1]
		self.collection[self.n - 1] = 0
		self.n = self.n - 1
		self.changeElement(0)
		return element
	
	#  Handles the request of displaying Tree elements
	def printTree(self) :
		print("\n Level Order Heap Element ")
		i = 0
		while (i < self.n) :
			print("  ", self.collection[i], end = "")
			i += 1
		
		print("\n Preorder ")
		self.preorder(0)
	

def main() :
	#  Number of elements in heap
	#  Set limit
	limit = 50
	#  Possible child
	k = 4
	heap = KAryHeap(limit, k)
	#  Add heap element
	heap.addElement(10)
	heap.addElement(7)
	heap.addElement(40)
	heap.addElement(2)
	heap.addElement(5)
	heap.addElement(15)
	heap.addElement(21)
	heap.addElement(35)
	heap.addElement(49)
	heap.addElement(38)
	heap.addElement(63)
	heap.addElement(19)
	# Max heap of K 4
	#         -----------------------   
	#         
	#                        63
	#         ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	#         │               │       │    │ 
	#         40              49      2    5
	#         |               │
	#     ┌‒‒‒┬‒‒‒┬‒‒‒┐   ┌‒‒‒┬‒‒‒┐
	#     │   │   │   │   │   │   │    
	#     7  15   21  35  10  38  19
	#     -------------------------------
	#             Constructed Tree               
	#         
	
	heap.printTree()
	print("\n Extract Max Element : ", heap.extractMax(), end = "")
	#  Extract Max Element
	#   -----------------------   
	#     
	#                        (49)
	#         ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	#         │               │       │    │ 
	#       (40)             (38)     2    5
	#         |               │
	#     ┌‒‒‒┬‒‒‒┬‒‒‒┐     ┌‒‒‒┐
	#     │   │   │   │     │   │      
	#     7  15   21  35    10  19  
	#     -------------------------------
	#             After remove max node              
	#         
	
	heap.printTree()

if __name__ == "__main__": main()

Output

 Level Order Heap Element
   63   40   49   2   5   7   15   21   35   10   38   19
 Preorder
   63   40   7   15   21   35   49   10   38   19   2   5
 Extract Max Element :  63
 Level Order Heap Element
   49   40   38   2   5   7   15   21   35   10   19
 Preorder
   49   40   7   15   21   35   38   10   19   2   5
#  Ruby program
#  K-ary Heap

class KAryHeap  
	# Define the accessor and reader of class KAryHeap  
	attr_reader :limit, :n, :k, :collection
	attr_accessor :limit, :n, :k, :collection
 
	
	#  Number of element
	
	#  Current element
	
	#  Number of child
	
	def initialize(limit, k) 
		#  Set How many number of elements possible in heap
		self.limit = limit
		#  Set intial no element in heap
		self.n = 0
		#  Set number of child nodes
		self.k = k
		#  Allocate memory of heap elements
		self.collection = Array.new(limit) {0}
	end

	#  Display pre order view of ternary tree
	def preorder(root) 
		if (root < self.n) 
			print("  ", self.collection[root])
			i = 1
			#  Recursive visit to child node
			while (i <= self.k) 
				self.preorder(self.k * root + i)
				i += 1
			end

		end

	end

	#  Swap two elements of heap collection
	def swap(first, second) 
		auxiliary = self.collection[first]
		self.collection[first] = self.collection[second]
		self.collection[second] = auxiliary
	end

	#  This are converting tree into valid max heap when insert new element
	def putElement(location) 
		root = (location - 1) / self.k
		while (root >= 0 && self.collection[location] > self.collection[root]) 
			self.swap(location, root)
			location = root
			root = (location - 1) / self.k
		end

	end

	#  Handles the request of adding  new heap element
	def addElement(data) 
		if (self.n + 1 >= self.limit) 
			print("\n Heap limit is exceeded When add new element")
			return
		end

		self.collection[self.n] = data
		self.n = self.n + 1
		self.putElement(self.n - 1)
	end

	#  After remove top of tree this are converted into a new max heap
	def changeElement(location) 
		update = -1
		i = 1
		while (i <= self.k) 
			if ((location * self.k) + i < self.n && self.collection[location] < self.collection[(location * self.k) + i]) 
				if (update == -1) 
					#  First largest child
					update = (location * self.k) + i
				elsif(self.collection[update] < self.collection[(location * self.k) + i]) 
					#  When previous child is smaller
					update = (location * self.k) + i
				end

			end

			i += 1
		end

		if (update >= 0) 
			#  Swap element
			self.swap(location, update)
			#  Check next updation
			self.changeElement(update)
		end

	end

	#  Remove the max element from the tree
	def extractMax() 
		if (self.n == 0) 
			print("\n Empty Heap ")
			return -1
		end

		element = self.collection[0]
		self.collection[0] = self.collection[self.n - 1]
		self.collection[self.n - 1] = 0
		self.n = self.n - 1
		self.changeElement(0)
		return element
	end

	#  Handles the request of displaying Tree elements
	def printTree() 
		print("\n Level Order Heap Element \n")
		i = 0
		while (i < self.n) 
			print("  ", self.collection[i])
			i += 1
		end

		print("\n Preorder \n")
		self.preorder(0)
	end

end

def main() 
	#  Number of elements in heap
	#  Set limit
	limit = 50
	#  Possible child
	k = 4
	heap = KAryHeap.new(limit, k)
	#  Add heap element
	heap.addElement(10)
	heap.addElement(7)
	heap.addElement(40)
	heap.addElement(2)
	heap.addElement(5)
	heap.addElement(15)
	heap.addElement(21)
	heap.addElement(35)
	heap.addElement(49)
	heap.addElement(38)
	heap.addElement(63)
	heap.addElement(19)
	# Max heap of K 4
	#         -----------------------   
	#         
	#                        63
	#         ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	#         │               │       │    │ 
	#         40              49      2    5
	#         |               │
	#     ┌‒‒‒┬‒‒‒┬‒‒‒┐   ┌‒‒‒┬‒‒‒┐
	#     │   │   │   │   │   │   │    
	#     7  15   21  35  10  38  19
	#     -------------------------------
	#             Constructed Tree               
	#         
	
	heap.printTree()
	print("\n Extract Max Element : ", heap.extractMax())
	#  Extract Max Element
	#   -----------------------   
	#     
	#                        (49)
	#         ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	#         │               │       │    │ 
	#       (40)             (38)     2    5
	#         |               │
	#     ┌‒‒‒┬‒‒‒┬‒‒‒┐     ┌‒‒‒┐
	#     │   │   │   │     │   │      
	#     7  15   21  35    10  19  
	#     -------------------------------
	#             After remove max node              
	#         
	
	heap.printTree()
end

main()

Output

 Level Order Heap Element 
  63  40  49  2  5  7  15  21  35  10  38  19
 Preorder 
  63  40  7  15  21  35  49  10  38  19  2  5
 Extract Max Element : 63
 Level Order Heap Element 
  49  40  38  2  5  7  15  21  35  10  19
 Preorder 
  49  40  7  15  21  35  38  10  19  2  5
/*
    Scala program
    K-ary Heap
*/
class KAryHeap(var limit: Int , var n: Int , var k: Int , var collection: Array[Int])
{
	def this(limit: Int, k: Int)
	{
		this(limit, 0, k, Array.fill[Int](limit)(0));
	}
	// Display pre order view of ternary tree
	def preorder(root: Int): Unit = {
		if (root < this.n)
		{
			print("  " + this.collection(root));
			var i: Int = 1;
			// Recursive visit to child node
			while (i <= this.k)
			{
				this.preorder(this.k * root + i);
				i += 1;
			}
		}
	}
	// Swap two elements of heap collection
	def swap(first: Int, second: Int): Unit = {
		var auxiliary: Int = this.collection(first);
		this.collection(first) = this.collection(second);
		this.collection(second) = auxiliary;
	}
	// This are converting tree into valid max heap when insert new element
	def putElement(position: Int): Unit = {
      	var location = position;
		var root: Int = ((location - 1) / this.k).toInt;
		while (root >= 0 && this.collection(location) > this.collection(root))
		{
			this.swap(location, root);
			location = root;
			root = ((location - 1) / this.k).toInt;
		}
	}
	// Handles the request of adding  new heap element
	def addElement(data: Int): Unit = {
		if (this.n + 1 >= this.limit)
		{
			print("\n Heap limit is exceeded When add new element");
			return;
		}
		this.collection(this.n) = data;
		this.n = this.n + 1;
		this.putElement(this.n - 1);
	}
	// After remove top of tree this are converted into a new max heap
	def changeElement(location: Int): Unit = {
		var update: Int = -1;
		var i: Int = 1;
		while (i <= this.k)
		{
			if ((location * this.k) + i < this.n && this.collection(location) < this.collection((location * this.k) + i))
			{
				if (update == -1)
				{
					// First largest child
					update = (location * this.k) + i;
				}
				else if (this.collection(update) < this.collection((location * this.k) + i))
				{
					// When previous child is smaller
					update = (location * this.k) + i;
				}
			}
			i += 1;
		}
		if (update >= 0)
		{
			// Swap element
			this.swap(location, update);
			// Check next updation
			this.changeElement(update);
		}
	}
	// Remove the max element from the tree
	def extractMax(): Int = {
		if (this.n == 0)
		{
			print("\n Empty Heap ");
			return -1;
		}
		var element: Int = this.collection(0);
		this.collection(0) = this.collection(this.n - 1);
		this.collection(this.n - 1) = 0;
		this.n = this.n - 1;
		this.changeElement(0);
		return element;
	}
	// Handles the request of displaying Tree elements
	def printTree(): Unit = {
		print("\n Level Order Heap Element \n");
		var i: Int = 0;
		while (i < this.n)
		{
			print("  " + this.collection(i));
			i += 1;
		}
		print("\n Preorder \n");
		this.preorder(0);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Number of elements in heap
		// Set limit
		var limit: Int = 50;
		// Possible child
		var k: Int = 4;
		var heap: KAryHeap = new KAryHeap(limit, k);
		// Add heap element
		heap.addElement(10);
		heap.addElement(7);
		heap.addElement(40);
		heap.addElement(2);
		heap.addElement(5);
		heap.addElement(15);
		heap.addElement(21);
		heap.addElement(35);
		heap.addElement(49);
		heap.addElement(38);
		heap.addElement(63);
		heap.addElement(19);
		/*Max heap of K 4
		        -----------------------   
		        
		                       63
		        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
		        │               │       │    │ 
		        40              49      2    5
		        |               │
		    ┌‒‒‒┬‒‒‒┬‒‒‒┐   ┌‒‒‒┬‒‒‒┐
		    │   │   │   │   │   │   │    
		    7  15   21  35  10  38  19
		    -------------------------------
		            Constructed Tree               
		        
		*/
		heap.printTree();
		print("\n Extract Max Element : " + heap.extractMax());
		/* Extract Max Element
		  -----------------------   
		    
		                       (49)
		        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
		        │               │       │    │ 
		      (40)             (38)     2    5
		        |               │
		    ┌‒‒‒┬‒‒‒┬‒‒‒┐     ┌‒‒‒┐
		    │   │   │   │     │   │      
		    7  15   21  35    10  19  
		    -------------------------------
		            After remove max node              
		        
		*/
		heap.printTree();
	}
}

Output

 Level Order Heap Element
  63  40  49  2  5  7  15  21  35  10  38  19
 Preorder
  63  40  7  15  21  35  49  10  38  19  2  5
 Extract Max Element : 63
 Level Order Heap Element
  49  40  38  2  5  7  15  21  35  10  19
 Preorder
  49  40  7  15  21  35  38  10  19  2  5
/*
    Swift 4 program
    K-ary Heap
*/
class KAryHeap
{
	var limit: Int;
	// Number of element
	var n: Int;
	// Current element
	var k: Int;
	// Number of child
	var collection: [Int];
	init(_ limit: Int, _ k: Int)
	{
		// Set How many number of elements possible in heap
		self.limit = limit;
		// Set intial no element in heap
		self.n = 0;
		// Set number of child nodes
		self.k = k;
		// Allocate memory of heap elements
		self.collection = Array(repeating: 0, count: limit);
	}
	// Display pre order view of ternary tree
	func preorder(_ root: Int)
	{
		if (root < self.n)
		{
			print("  ", self.collection[root], terminator: "");
			var i: Int = 1;
			// Recursive visit to child node
			while (i <= self.k)
			{
				self.preorder(self.k * root + i);
				i += 1;
			}
		}
	}
	// Swap two elements of heap collection
	func swap(_ first: Int, _ second: Int)
	{
		let auxiliary: Int = self.collection[first];
		self.collection[first] = self.collection[second];
		self.collection[second] = auxiliary;
	}
	// This are converting tree into valid max heap when insert new element
	func putElement(_ position: Int)
	{	var location = position;
		var root: Int = (location - 1) / self.k;
		while (root >= 0 && self.collection[location] > self.collection[root])
		{
			self.swap(location, root);
			location = root;
			root = (location - 1) / self.k;
		}
	}
	// Handles the request of adding  new heap element
	func addElement(_ data: Int)
	{
		if (self.n + 1 >= self.limit)
		{
			print("\n Heap limit is exceeded When add new element", terminator: "");
			return;
		}
		self.collection[self.n] = data;
		self.n = self.n + 1;
		self.putElement(self.n - 1);
	}
	// After remove top of tree this are converted into a new max heap
	func changeElement(_ location: Int)
	{
		var update: Int = -1;
		var i: Int = 1;
		while (i <= self.k)
		{
			if ((location * self.k) + i < self.n 
                && self.collection[location] < self.collection[(location * self.k) + i])
			{
				if (update == -1)
				{
					// First largest child
					update = (location * self.k) + i;
				}
				else if (self.collection[update] < self.collection[(location * self.k) + i])
				{
					// When previous child is smaller
					update = (location * self.k) + i;
				}
			}
			i += 1;
		}
		if (update >= 0)
		{
			// Swap element
			self.swap(location, update);
			// Check next updation
			self.changeElement(update);
		}
	}
	// Remove the max element from the tree
	func extractMax()->Int
	{
		if (self.n == 0)
		{
			print("\n Empty Heap ", terminator: "");
			return -1;
		}
		let element: Int = self.collection[0];
		self.collection[0] = self.collection[self.n - 1];
		self.collection[self.n - 1] = 0;
		self.n = self.n - 1;
		self.changeElement(0);
		return element;
	}
	// Handles the request of displaying Tree elements
	func printTree()
	{
		print("\n Level Order Heap Element ");
		var i: Int = 0;
		while (i < self.n)
		{
			print("  ", self.collection[i], terminator: "");
			i += 1;
		}
		print("\n Preorder ");
		self.preorder(0);
	}
}
func main()
{
	// Number of elements in heap
	// Set limit
	let limit: Int = 50;
	// Possible child
	let k: Int = 4;
	let heap: KAryHeap = KAryHeap(limit, k);
	// Add heap element
	heap.addElement(10);
	heap.addElement(7);
	heap.addElement(40);
	heap.addElement(2);
	heap.addElement(5);
	heap.addElement(15);
	heap.addElement(21);
	heap.addElement(35);
	heap.addElement(49);
	heap.addElement(38);
	heap.addElement(63);
	heap.addElement(19);
	/*Max heap of K 4
	        -----------------------   
	        
	                       63
	        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	        │               │       │    │ 
	        40              49      2    5
	        |               │
	    ┌‒‒‒┬‒‒‒┬‒‒‒┐   ┌‒‒‒┬‒‒‒┐
	    │   │   │   │   │   │   │    
	    7  15   21  35  10  38  19
	    -------------------------------
	            Constructed Tree               
	        
	*/
	heap.printTree();
	print("\n Extract Max Element : ", heap.extractMax(), terminator: "");
	/* Extract Max Element
	  -----------------------   
	    
	                       (49)
	        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	        │               │       │    │ 
	      (40)             (38)     2    5
	        |               │
	    ┌‒‒‒┬‒‒‒┬‒‒‒┐     ┌‒‒‒┐
	    │   │   │   │     │   │      
	    7  15   21  35    10  19  
	    -------------------------------
	            After remove max node              
	        
	*/
	heap.printTree();
}
main();

Output

 Level Order Heap Element
   63   40   49   2   5   7   15   21   35   10   38   19
 Preorder
   63   40   7   15   21   35   49   10   38   19   2   5
 Extract Max Element :  63
 Level Order Heap Element
   49   40   38   2   5   7   15   21   35   10   19
 Preorder
   49   40   7   15   21   35   38   10   19   2   5
/*
    Kotlin program
    K-ary Heap
*/
class KAryHeap
{
	var limit: Int;
	var n: Int;
	var k: Int;
	var collection: Array <Int> ;
	constructor(limit: Int, k: Int)
	{
		// Set How many number of elements possible in heap
		this.limit = limit;
		// Set intial no element in heap
		this.n = 0;
		// Set number of child nodes
		this.k = k;
		// Allocate memory of heap elements
		this.collection = Array(limit)
		{
			0
		};
	}
	// Display pre order view of ternary tree
	fun preorder(root: Int): Unit
	{
		if (root < this.n)
		{
			print("  " + this.collection[root]);
			var i: Int = 1;
			// Recursive visit to child node
			while (i <= this.k)
			{
				this.preorder(this.k * root + i);
				i += 1;
			}
		}
	}
	// Swap two elements of heap collection
	fun swap(first: Int, second: Int): Unit
	{
		var auxiliary: Int = this.collection[first];
		this.collection[first] = this.collection[second];
		this.collection[second] = auxiliary;
	}
	// This are converting tree into valid max heap when insert new element
	fun putElement(position: Int): Unit
	{
      	var location = position;
		var root: Int = (location - 1) / this.k;
		while (root >= 0 && this.collection[location] > this.collection[root])
		{
			this.swap(location, root);
			location = root;
			root = (location - 1) / this.k;
		}
	}
	// Handles the request of adding  new heap element
	fun addElement(data: Int): Unit
	{
		if (this.n + 1 >= this.limit)
		{
			print("\n Heap limit is exceeded When add new element");
			return;
		}
		this.collection[this.n] = data;
		this.n = this.n + 1;
		this.putElement(this.n - 1);
	}
	// After remove top of tree this are converted into a new max heap
	fun changeElement(location: Int): Unit
	{
		var update: Int = -1;
		var i: Int = 1;
		while (i <= this.k)
		{
			if ((location * this.k) + i < this.n && this.collection[location] < this.collection[(location * this.k) + i])
			{
				if (update == -1)
				{
					// First largest child
					update = (location * this.k) + i;
				}
				else if (this.collection[update] < this.collection[(location * this.k) + i])
				{
					// When previous child is smaller
					update = (location * this.k) + i;
				}
			}
			i += 1;
		}
		if (update >= 0)
		{
			// Swap element
			this.swap(location, update);
			// Check next updation
			this.changeElement(update);
		}
	}
	// Remove the max element from the tree
	fun extractMax(): Int
	{
		if (this.n == 0)
		{
			print("\n Empty Heap ");
			return -1;
		}
		var element: Int = this.collection[0];
		this.collection[0] = this.collection[this.n - 1];
		this.collection[this.n - 1] = 0;
		this.n = this.n - 1;
		this.changeElement(0);
		return element;
	}
	// Handles the request of displaying Tree elements
	fun printTree(): Unit
	{
		print("\n Level Order Heap Element \n");
		var i: Int = 0;
		while (i < this.n)
		{
			print("  " + this.collection[i]);
			i += 1;
		}
		print("\n Preorder \n");
		this.preorder(0);
	}
}
fun main(args: Array < String > ): Unit
{
	// Number of elements in heap
	// Set limit
	var limit: Int = 50;
	// Possible child
	var k: Int = 4;
	var heap: KAryHeap = KAryHeap(limit, k);
	// Add heap element
	heap.addElement(10);
	heap.addElement(7);
	heap.addElement(40);
	heap.addElement(2);
	heap.addElement(5);
	heap.addElement(15);
	heap.addElement(21);
	heap.addElement(35);
	heap.addElement(49);
	heap.addElement(38);
	heap.addElement(63);
	heap.addElement(19);
	/*Max heap of K 4
	        -----------------------   
	        
	                       63
	        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	        │               │       │    │ 
	        40              49      2    5
	        |               │
	    ┌‒‒‒┬‒‒‒┬‒‒‒┐   ┌‒‒‒┬‒‒‒┐
	    │   │   │   │   │   │   │    
	    7  15   21  35  10  38  19
	    -------------------------------
	            Constructed Tree               
	        
	*/
	heap.printTree();
	print("\n Extract Max Element : " + heap.extractMax());
	/* Extract Max Element
	  -----------------------   
	    
	                       (49)
	        ┌‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒┬‒‒‒‒‒‒‒┬‒‒‒‒┐
	        │               │       │    │ 
	      (40)             (38)     2    5
	        |               │
	    ┌‒‒‒┬‒‒‒┬‒‒‒┐     ┌‒‒‒┐
	    │   │   │   │     │   │      
	    7  15   21  35    10  19  
	    -------------------------------
	            After remove max node              
	        
	*/
	heap.printTree();
}

Output

 Level Order Heap Element
  63  40  49  2  5  7  15  21  35  10  38  19
 Preorder
  63  40  7  15  21  35  49  10  38  19  2  5
 Extract Max Element : 63
 Level Order Heap Element
  49  40  38  2  5  7  15  21  35  10  19
 Preorder
  49  40  7  15  21  35  38  10  19  2  5

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