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
{
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);

/* 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
{
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);
/*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
{
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);
/*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
{
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);
/*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
{
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);
/*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
{
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);
/*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
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)
# 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_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
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)
# 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);
/*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
{
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);
/*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
{
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);
/*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.

Categories
Relative Post