K-ary heap

Last Updated on July 20, 2022 by Ria Pathak

K-ary heaps are similar to the binary heap (where K = 2) just having one difference that instead of 2 child nodes, there can be k child nodes for every node in the heap.

It follows the following 2 properties:

1. It is nearly like a complete binary tree, i.e. all the levels are having maximum number of nodes except the last level, which is filled from left to right.
2. Just like a binary heap, it is further categorized into two types:
   • Max K – ary heap (Value of node at root is greater than its left and right child nodes).
   • Min K – ary heap (Value of node at root is smaller than its left and right child nodes).

Applications of k-ary Heap:

• In the implementation of a priority queue, the k-ary heap (O(log_kn)) is faster for decreasing key operations as compared to the binary heap(O(log₂n)). But it increases the complexity of the extractMin() operation from (O(logkn)) when the binary heap is used to (O(klog_kn)) when the k-ary heap is used for the priority queue. So, it will be more efficient for using the k-ary heap where a decreased priority queue is used. For example, Prim’s algorithm for minimum spanning tree.
• K-ary heap has better handling for the memory cache behavior than the binary heap which allows running more quickly in practice although it is having a bigger worst-case time complexity of both extractMin() and delete() operation (both being (O(klog_kn))).

Implementation

Consider 0-based indexing in the array, the array will represent a K-ary heap such that for any node:

• Parent of the node which is at index i is located at index (i-1)/k.
• Child nodes of index i are at indices (ki)+1, (ki)+2….(k*i)+k.
• The last non-leaf node of the heap will be located at index (n-2)/k.

buildHeap(): This function is used for building the heap.
In this function, iteration will be started from the last non-leaf node to the root node, and for each iteration restoreDown (or maxHeapify) function will be called that will restore the passed index at the correct position of the heap by shifting the node down in the k-ary heap which is built in a bottom-up manner.

restoreDown() (or maxHeapify): This function is used to maintain the property of the heap.
In this function, iteration will be done for finding the maximum from all the children nodes, compare the value of the maximum child node value with its own, and swap if the max(value of all children)>(value at a node). This step will be repeated until the node is restored to its original position in the heap.

extractMax(): This function is used for extracting the root node.
In the max k-ary heap, the largest element is stored in the root. This function will return the root node, and copies the value of the last node to the first node, and calls the restore down function on the first node to maintain the property of the heap.

insert(): This function is used to insert the node into the heap.
Firstly, the node will be inserted at the last position, then the restoreUp function will be called on the given index to restore the node to its proper position in the heap. restoreUp function will iteratively do a comparison between the given node with its parent, to maintain the property of max heap, the node is swapped with its parent when its value is greater than its parent.

Code Implementation

#include<bits/stdc++.h>

using namespace std;

void restoreDown(int arr[], int len, int index,
										int k)
{
	int child[k+1];

	while (1)
	{
		for (int i=1; i<=k; i++)
			child[i] = ((k*index + i) < len) ?
					(k*index + i) : -1;

		int max_child = -1, max_child_index ;

		for (int i=1; i<=k; i++)
		{
			if (child[i] != -1 &&
				arr[child[i]] > max_child)
			{
				max_child_index = child[i];
				max_child = arr[child[i]];
			}
		}

		if (max_child == -1)
			break;

		if (arr[index] < arr[max_child_index])
			swap(arr[index], arr[max_child_index]);

		index = max_child_index;
	}
}

void restoreUp(int arr[], int index, int k)
{
	int parent = (index-1)/k;
	while (parent>=0)
	{
		if (arr[index] > arr[parent])
		{
			swap(arr[index], arr[parent]);
			index = parent;
			parent = (index -1)/k;
		}

		else
			break;
	}
}

void buildHeap(int arr[], int n, int k)
{
	for (int i= (n-1)/k; i>=0; i--)
		restoreDown(arr, n, i, k);
}

void insert(int arr[], int* n, int k, int elem)
{
	arr[*n] = elem;
	*n = *n+1;

	restoreUp(arr, *n-1, k);
}

int extractMax(int arr[], int* n, int k)
{

	int max = arr[0];

	arr[0] = arr[*n-1];
	*n = *n-1;
	restoreDown(arr, *n, 0, k);

	return max;
}

int main()
{
	const int capacity = 100;
	int arr[capacity] = {4, 5, 6, 7, 8, 9, 10};
	int n = 7;
	int k = 3;

	buildHeap(arr, n, k);

	printf("Built Heap : \n");
	for (int i=0; i<n; i++)
		printf("%d ", arr[i]);

	int element = 3;
	insert(arr, &n, k, element);

	printf("\n\nHeap after insertion of %d: \n",
			element);
	for (int i=0; i<n; i++)
		printf("%d ", arr[i]);

	printf("\n\nExtracted max is %d",
				extractMax(arr, &n, k));

	printf("\n\nHeap after extract max: \n");
	for (int i=0; i<n; i++)
		printf("%d ", arr[i]);

	return 0;
}

Output:
Built Heap :
10 9 6 7 8 4 5

Heap after insertion of 3:
10 9 6 7 8 4 5 3

Extracted max is 10

Heap after extract max:
9 8 6 7 3 4 5

Time Complexity Analysis

• The time complexity for the buildHeap function is O(n) (similar to binary heap).
• The time complexity for the restoreDown function is O(klogkn)).
• The time complexity for the insert and decreaseKey function is O(logkn)).
• Since extractMax calls the restoreDown function, the time complexity will be O(klogkn)).
• In the k-ary heap, the maximum height will be logkn for n nodes present in it. Therefore, the restoreUp function will be called for maximum logkn times(in each iteration, the node will move upward which is the case of restoreUp, or moves downward which is the case of restoreDown).

This article tried to discuss K-ary heap. Hope this blog helps you understand the concept. To practice more problems feel free to check MYCODE | Competitive Programming at Prepbytes.