K-ary Heap

Operations

constructHeap:

This function constructs a heap from a given array(i.e., an arbitrary complete K-ary tree) and simultaneously represents the heap in the given array sequentially.

• In this operation, we will move a node to its correct position in the heap array.
• A loop runs from the last non-leaf node in the given tree, which is at index (n-1)/k (where n is the number of nodes or size of the array)
• We will not consider leaf nodes as they already satisfy the heap property.
• For each non-leaf node, Heapify() function is called to move a node to its correct position in the heap array.

maxHeapify: 

This function is used to build max-heap property in the tree.

• It runs a loop to move the given value to its correct position in the heap array.
• At first, it finds max among all children of the given node 
• Then compares max child value with given node value; if max(value of child nodes) > value of the given node, then the values are swapped.
• This process repeats until the given value is moved to its correct position in the array and the heap.

Similarly, to construct a min-heap, one can use the minHeapify function.

Insert: 

In this operation, a new node can be inserted into the heap so that the heap property of the tree remains unaltered after insertion

• The new value is inserted at the last position of the given array 
• Then using the heapify function, the node is moved to its proper position in a heap as well as in the array.

heapify: 

• This function iteratively compares the value of a given node with its parent.
• For max-heap, if the given node value is greater than the parent’s value, they are swapped.

extractMax: 

This function is the most common operation on any heap. 

• It extracts the max value from the heap, i.e., root’s value at 1st index of the array
• restores the heap property from remaining after copying the last node to the 1st index. Here maxHeapify function is used for max-heap.

Code

// C++ program to demonstrate all operations of k-ary Heap #include<bits/stdc++.h> using namespace std; // arr[] -- Array that stores heap // n -- Size of array // index -- index of the element to be restored void maxHeapify(int arr[], int n, int index,int k) { // array to store indices of the children of the given node int child[k+1]; while (1) { // child[i]=-1 if the index of the node is beyound n for (int i=1; i<=k; i++) child[i] = ((k*index + i) < n) ? (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]]; } } // given node is a leaf node if (max_child == -1) break; // swap only if the value of max_child_index // is greater than the value of the given node if (arr[index] < arr[max_child_index]) swap(arr[index], arr[max_child_index]); index = max_child_index; } } // function to construct  a k-ary heap of arr[0..n-1] . void constructHeap(int arr[], int n, int k) { // Heapify all internal nodes starting from last // non-leaf node the up to the root node // and calling maxHeapify  on each for (int i= (n-1)/k; i>=0; i--) maxHeapify(arr, n, i, k); } // restores a given node at its proper position in the heap.  void heapify(int arr[], int index, int k) { int parent = (index-1)/k; //index of parent node // loop till root node in case the // value inserted is the maximum  while (parent>=0) { if (arr[index] > arr[parent]) { swap(arr[index], arr[parent]); index = parent; // new index of given node parent = (index -1)/k;  //updating index parent node } // node restored at the correct position else break; } } // function to insert a value in a K-ary Heap.  void insert(int arr[], int &n, int k, int value) { // insert the new value in the last position arr[n] = value; // increase heap size by 1 n = n+1; // call heapify on the last index heapify(arr, n-1, k); } // function that returns the value of root node of //  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 maxHeapify on the root node to restore // it to the correct position in the heap maxHeapify(arr, n, 0, k); return max; } // Driver program int main() { const int size = 10; int arr[size] = {2, 3, 4, 5, 6, 7, 10}; int n = 7; int k = 3; constructHeap(arr, n, k); cout<<"Construct Max Heap : "<<endl; for (int i=0; i<n; i++) cout<<arr[i]<<" "; int value = 1; insert(arr, n, k, value); cout<<"\n\nHeap after insertion of "<<value<<endl; for (int i=0; i<n; i++) cout<<arr[i]<<" "; cout<<"\n\nExtracted max is "<<extractMax(arr, n, k); cout<<"\n\nHeap after extract max: \n"; for (int i=0; i<n; i++) cout<<arr[i]<<" "; return 0; } You can also try this code with Online C++ Compiler Run Code

Output

Complexity analysis

• constructHeap takes O(n) time where n is the total number of nodes. For detailed proof, refer to this.

• maxHeapify takes O( klogkn) time at the worst case as for every iteration, it is called for at most k children, and the iteration can be logkn times.

• insert operation takes O(logkn) time as heapify can run at most logkn times

• extractMax takes O( klogkn) time as it calls maxHeapify once.

FAQs

1. What is meant by Complete Tree?
   In this type of tree, all levels except the last level must be completely filled. In the last level, all nodes must be as left as possible.
    
2. What is Binary Heap?
   Binary Heap is a complete binary tree, and it is either max-heap(value of parent node is greater than or equal to the value  of all child nodes, this property recursively true for all nodes) or min-heap(the value of the parent node is lesser than or equal to the value of all child nodes, which is recursively true for all nodes).
    
3. How is K-ary Heap related to Binary Heap?
   K-ary Heap is a generalized version of Binary Heap. In the case of Binary      Binary Heap, K=2 i.e.., for each node, at most, two children are there.
    
4. Application of K-ary Heap.
   It is used for implementing a priority queue.
   K-ary Heap also shows better memory cache behavior.
   In Dijkstra's algorithm for shortest paths and Prim's algorithm for minimum spanning trees K-ary Heap is used.
    
5. What is max min-heap?
   For a max heap tree, the parent node’s value is greater than or equal to the value of all child nodes, this property recursively true for all nodes.
   For min-heap, the parent node’s value is lesser than or equal to the value of all child nodes, this property recursively true for all nodes.  

Key Takeaways

This article discussed the concepts of K-ary Heap, implementation of  K-ary Heap, and various operations that can be performed on a  K-ary Heap. 

The blog also tried to provide a better understanding of the time complexities of various operations and applications of K-ary Heap. 

To learn more, head over right now to Coding Ninjas Studio to practice important heap-based problems and crack your interviews like a Ninja!

Happy learning!