Prerequisites – Binary piles
The K-ary heap is a generalization of the binary heap (K = 2), where each node has K child nodes instead of 2 child nodes. Just like the binary pile, it has two properties:
1) Almost complete binary tree, with the largest number of nodes at all levels except the last node (padded from left to right).
2) Like Binary Heap, it can be divided into two categories: (a) Maximum K-ary heap (the key of the root node is greater than all descendants, and applies recursively to all nodes). (b) Minimum k-base heap (the key of the root node is less than that of all descendants, and applies recursively to all nodes)
Example:
3-ary max heap - root node is maximum
of all nodes
10
/| \
7 9 8
/| \ /
4 6 5 7
3-ary min heap -root node is minimum
of all nodes
10
/| \
12 11 13
/| \
14 15 18The height of a complete k-element tree with n nodes is given by log.
Applications of K-ary heaps:
- The K-ary heap uses a priority queue when executing compared to the binary heap, allowing for faster reduction of key operations (O(log2n) for the binary heap vs O(logkn) for the K-ary heap). However, this leads to an increase in the complexity of the extractMin() operation to the point where O(k logKn) and O(log2n) use the binary heap for priority queues. This makes the K-ary heap more efficient in algorithms where priority reduction operations are more common than extractMin() operations. Dikstra’s single-source shortest path and Primus minimum spanning tree algorithm
- K-ary heaps have better memory caching behavior than binary heaps, which makes them run faster in practice, although it runs longer in the worst-case case of both extractMin() and delete() operations (both O(k logkn)).
implement
Assuming an array index based on 0, the array represents a K-ary heap, so for any node, we consider:
- The parent node of the node of index i (except the root node) is located at index (i-1)/k
- The indexes of the children of a node with index i are (k * i)+1, (k * i)+2…. (k * i)+ k
- The last non-leaf node of the heap of size n is at the index (n-2)/k
buildHeap(): Build heap from input array.
The function runs a loop from the last non-leaf node all the way to the root node, calling the function restoreDown (also known as maHeapify) for each index, which restores the passed index to the correct position of the heap by moving the node down in a bottom-up fashion in the K-ary heap.
Why do we start the loop with the last non-leaf node?
Because all nodes after this are leaf nodes, they will not satisfy any of the requirements of the children, and therefore can satisfy the heap property, and are therefore already the root of the largest heap in the K-ary.
restoreDown() (or maxHeapify): Used to maintain heap properties.
It runs a loop that finds the maximum value of all child nodes of all nodes, compares it to its own value, and swaps that value if max (the value of all child nodes) > (the value of the node). Repeat this step until the node returns to its original position in the heap.
extractMax(): extracts the root node.
The K-dollar max heap stores the largest element in its root. It returns the root node, copies the last node to the first node, invokes restore on the first node, and thus maintains the heap properties.
insert(): Inserts the node into the heap
This can be achieved by inserting a node at the last location and calling restoreUp() on a given index to restore the node to its proper location in the heap. restoreUp() iteratively compares a given node to its parent node, because in the maximum heap, the parent node is always greater than or equal to its children, so the node will only be swapped with its parent node if its key is greater than the parent node.
Combining the above, here is the C++ implementation of the K-ary heap.
//C++ program to demonstrate all operations of
//k-ary Heap
#include<bits/stdc++.h>
using namespace std;
//function to heapify (or restore the max- heap
//property). This is used to build a k-ary heap
//and in extractMin()
//att[] -- Array that stores heap
//len -- Size of array
//index -- index of element to be restored
// (or heapified)
void restoreDown( int arr[], int len, int index, int k)
{
//child array to store indexes of all
//the children of given node
int child[k+1];
while (1)
{
//child[i]=-1 if the node is a leaf
//children (no children)
for ( int i=1; i<=k; i++)
child[i] = ((k*index + i) <len) ?
(k*index + i) : -1;
//max_child stores the maximum child and
//max_child_index holds its index
int max_child = -1, max_child_index ;
//loop to find the maximum of all
//the children of a given node
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]];
}
}
//leaf node
if (max_child == -1)
break ;
//swap only if the key of max_child_index
//is greater than the key of node
if (arr[index] <arr[max_child_index])
swap(arr[index], arr[max_child_index]);
index = max_child_index;
}
}
//Restores a given node up in the heap. This is used
//in decreaseKey() and insert()
void restoreUp( int arr[], int index, int k)
{
//parent stores the index of the parent variable
//of the node
int parent = (index-1)/k;
//Loop should only run till root node in case the
//element inserted is the maximum restore up will
//send it to the root node
while (parent>=0)
{
if (arr[index]> arr[parent])
{
swap(arr[index], arr[parent]);
index = parent;
parent = (index -1)/k;
}
//node has been restored at the correct position
else
break ;
}
}
//Function to build a heap of arr[0..n-1] and alue of k.
void buildHeap( int arr[], int n, int k)
{
//Heapify all internal nodes starting from last
//non-leaf node all the way upto the root node
//and calling restore down on each
for ( int i= (n-1)/k; i>=0; i--)
restoreDown(arr, n, i, k);
}
//Function to insert a value in a heap. Parameters are
//the array, size of heap, value k and the element to
//be inserted
void insert( int arr[], int * n, int k, int elem)
{
//Put the new element in the last position
arr[*n] = elem;
//Increase heap size by 1
*n = *n+1;
//Call restoreUp on the last index
restoreUp(arr, *n-1, k);
}
//Function that returns the key of root node of
//the heap and then restores the heap property
//of the remaining nodes
int extractMax( int arr[], int * n, int k)
{
//Stores the key of root node to be returned
int max = arr[0];
//Copy the last node's key to the root node
arr[0] = arr[*n-1];
//Decrease heap size by 1
*n = *n-1;
//Call restoreDown on the root node to restore
//it to the correct position in the heap
restoreDown(arr, *n, 0, k);
return max;
}
//Driver program
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;
}The output is as follows
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 5Time complexity analysis
- For a k-element heap with n nodes, the maximum height of a given heap will be logkn. As a result, restoreUp() runs the maximum logkn time (in each iteration, restoreUp() moves the node up one level and restoreDown down one level).
- restoreDown() recursively calls itself for k children. So the time complexity of this function is O(k logkn).
- The Insert and reduceKey() operations call restoreUp() once. So the complexity is O(logkn).
- Since extractMax() calls restoreDown() once, its complexity is O(k logkn)
- The time complexity of building the heap is O(n) (the analysis is similar to that of a binary heap)
If you find anything incorrect, or would like to share more information about the above topics, please leave a comment.
