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:
-
Nearly complete binary tree, with all levels having maximum number of nodes except the last, which is filled in left to right manner.
-
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)
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(log2n)) for binary heap vs O(logkn) for K-ary heap). Nevertheless, it causes the complexity of extractMin() operation to increase to O(k log kn) as compared to the complexity of O(log2n) 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 kn) ).
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 (ki)+1 , (ki)+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.