Prerequisite – Binary Heap

K-ary heaps are a generalization of binary heap(K=2) in which each node have K children instead of 2. Just like binary heap, it follows two properties:

1) Nearly complete binary tree, with all levels having maximum number of nodes except the last, which is filled in left to right manner.

2) Like Binary Heap, it can be divided into two categories: (a) Max k-ary heap (key at root is greater than all descendants and same is recursively true for all nodes). (b) Min k-ary heap (key at root is lesser than all descendants and same is recursively true for all nodes)

Examples:

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 18

The height of a complete k-ary tree with n-nodes is given by log_{k}n.

**Applications of K-ary Heap**:

- K-ary heap when used in the implementation of priority queue allows faster decrease key operation as compared to binary heap ( O(log
_{2}n)) for binary heap vs O(log_{k}n) for K-ary heap). Nevertheless, it causes the complexity of extractMin() operation to increase to O(k log_{k}n) as compared to the complexity of O(log_{2}n) when using binary heaps for priority queue. This allows K-ary heap to be more efficient in algorithms where decrease priority operations are more common than extractMin() operation.Example: Dijkstra’s algorithm for single source shortest path and Prim’s algorithm for minimum spanning tree - K-ary heap has better memory cache behaviour than a binary heap which allows them to run more quickly in practice, although it has a larger worst case running time of both extractMin() and delete() operation (both being O(k log
_{k}n) ).

**Implementation**

Assuming 0 based indexing of array, an array represents a K-ary heap such that for any node we consider:

- Parent of the node at index i (except root node) is located at index (i-1)/k
- Children of the node at index i are at indices (k*i)+1 , (k*i)+2 …. (k*i)+k
- The last non-leaf node of a heap of size n is located at index (n-2)/k

**buildHeap()** : Builds a heap from an input array.

This function runs a loop starting from the last non-leaf node all the way upto the root node, calling a function restoreDown(also known as maHeapify) for each index that restores the passed index at the correct position of the heap by shifting the node down in the K-ary heap building it in a bottom up manner.

*Why do we start the loop from the last non-leaf node ?*

Because all the nodes after that are leaf nodes which will trivially satisfy the heap property as they don’t have any children and hence, are already roots of a K-ary max heap.

**restoreDown() (or maxHeapify)** : Used to maintain heap property.

It runs a loop where it finds the maximum of all the node’s children, compares it with its own value and swaps if the max(value of all children) > (value at node). It repeats this step until the node is restored into its original position in the heap.

**extractMax() : ** Extracting the root node.

A k-ary max heap stores the largest element in its root. It returns the root node, copies last node to the first, calls restore down on the first node thus maintaining the heap property.

**insert() : ** Inserting a node into the heap

This can be achieved by inserting the node at the last position and calling restoreUp() on the given index to restore the node at its proper position in the heap. restoreUp() iteratively compares a given node with its parent, since in a max heap the parent is always greater than or equal to its children nodes, the node is swapped with its parent only when its key is greater than the parent.

Combining the above, following is the C++ implementation of 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 :
"
``` `); ` ` ` `for` `(` `int` `i=0; i<n; i++) ` ` ` `printf` `(` `"%d "` `, arr[i]); ` ` ` ` ` `int` `element = 3; ` ` ` `insert(arr, &n, k, element); ` ` ` ` ` `printf` `(` ```
"
Heap after insertion of %d:
"
``` `, ` ` ` `element); ` ` ` `for` `(` `int` `i=0; i<n; i++) ` ` ` `printf` `(` `"%d "` `, arr[i]); ` ` ` ` ` `printf` `(` ```
"
Extracted max is %d"
``` `, ` ` ` `extractMax(arr, &n, k)); ` ` ` ` ` `printf` `(` ```
"
Heap after extract max:
"
``` `); ` ` ` `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**

- For a k-ary heap, with n nodes the maximum height of the given heap will be log
_{k}n. So restoreUp() run for maximum of log_{k}n times (as at every iteration the node is shifted one level up is case of restoreUp() or one level down in case of restoreDown). - restoreDown() calls itself recursively for k children. So time complexity of this functions is O(k log
_{k}n). - Insert and decreaseKey() operations call restoreUp() once. So complexity is O(log
_{k}n). - Since extractMax() calls restoreDown() once, its complexity O(k log
_{k}n) - Time complexity of build heap is O(n) (Analysis is similar to binary heap)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

## leave a comment

## 0 Comments