Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Implementation (Max Heap)
2.1.
Code in C++
2.2.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is the difference between a tree and a graph?
3.2.
What is a priority queue?
3.3.
What is the difference between heapify up and heapify down?
3.4.
What are the applications of N-ary heaps?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

N-ary Heap

Author Gaurish Anand
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Heap and Priority Queue

Introduction

Before beginning, let's recap what a complete binary tree and binary heap are. 

complete binary tree is a tree in which each node can have a max of two children, and all the levels should be completely filled except for the last level, where nodes should be filled from left to right. For example tree in the first image is not a complete binary tree.

For a detailed understanding of heaps, check out Understanding Heap Data Structure
 

complete binary tree


A binary Heap is a complete binary tree where nodes are in a specific order depending upon whether it is a max heap or a min-heap.
You can go through this article to learn more about the binary heap data structure.

N-ary heaps are similar to binary heaps. They are a generalized version of binary heaps. Unlike binary heap, n-ary trees can have a maximum of n children instead of 2. N-ary heaps have the following properties: 

  1. It is a complete n-ary tree where all the levels are filled except for the last level,  where nodes are filled from left to right.
  2. N-ary heaps are of 2 types: 
    1. Min N-ary Heap: The value at each node should be smaller than its children. 
min n-ary heap
  1. Max N-ary Heap: The value at each node should be greater than its children.    
heap
  1.  

Implementation (Max Heap)

We will store the n-ary heap in the form of an array where: 

  1. The maximum value node will be at the 0th index.
  2. The parent of a node at the ith index will be at (i-1)/k.
  3. The children of a node at the ith index will be at indices: (k*i)+1, (k*i)+2 … (k*i)+k.
     

getMax(): It returns the maximum element in the heap

isEmpty(): It returns true if the heap is empty.

Insert(): It inserts a new element in a heap. The operation to insert an element in an n-ary heap is similar to inserting a value in a binary heap. First, insert the element at the end of the tree. Then heapify upwards, i.e., traverse until the parent is smaller than the element inserted.

removeMax(): To delete the max key, we replace the key at the 0th index with the last element and pop out the last element. Then we will heapify downward until we reach a stage where all the node's children are smaller than the parent node.

Code in C++

#include<iostream>
#include<climits>
#include<vector>
using namespace std;

// implementation of n-ary max heap
class n_ary_heap{
	int n;
public:
	vector<int> pq;
	// constructors
    n_ary_heap(){
        n = 2; // by default - binary heap
    }
    n_ary_heap(int k){
        n = k;
    }

    // get the maximum value from the heap
    int getMax() {
        if(pq.size()==0){
            // no element
            return INT_MIN;
        }
        return pq[0];
    }

    bool isEmpty() {
        if(pq.size()==0){
            return true;
        }else{
            return false;
        }
    }

    // inserting a value in the heap
    void insert(int value) {
        // first insert it at the bottom
        pq.push_back(value);
        
        // Now heapify up till we place the value at the correct position
        int childrenIndex = pq.size()-1;
        int parentIndex = (childrenIndex-1)/n;
        while(parentIndex>=0 && pq[childrenIndex]>pq[parentIndex]){
            // since the value at the childrenIndex is greater and it is max heap, so we should swap
            swap(pq[childrenIndex],pq[parentIndex]);
            
            childrenIndex = parentIndex;
            parentIndex = (childrenIndex-1)/n;
        }
    }

    // removing the maximum element from the heap - which will be at the top in case of a max heap
    void removeMax() {
        pq[0] = pq[pq.size()-1];
        pq.pop_back();
        
        int parentIndex = 0;
      
        while(1){
            int largestValueIndex = parentIndex;
            
            // visit all its children and find the maximum value child among them
            for(int i=n*parentIndex+1; i<=(n*parentIndex + n) && i<pq.size();i++){
                if(pq[largestValueIndex]<pq[i]){
                    largestValueIndex = i;
                }
            }
            
            if(largestValueIndex==parentIndex){
                break;
            }else{
                // if the largest index is not the parent index, we need to heapify down
                swap(pq[parentIndex],pq[largestValueIndex]);
                parentIndex = largestValueIndex;
            }
        }
    }
};


int main(){
	n_ary_heap max_heap(3);

	vector<int> arr{4, 5, 6, 7, 8, 9, 10};

	// insert all the elements in the n-ary heap one by one
	for(int i=0;i<arr.size();i++){
		max_heap.insert(arr[i]);
	}

	// 	    Heap after inserting all the elements
	//        10
	//       / | \
	//      9  5  6
	//    / | \
	//   4  7  8

	cout<<"The maximum Element in the heap is: "<<max_heap.getMax()<<endl;

	max_heap.removeMax();
	cout<<"The Maximum Element after removing the previous max in the heap is: "<<max_heap.getMax()<<endl;

	// 	    Heap after removing the max element
	//         9
	//       / | \
	//      8  5  6
	//    / | 
	//   4  7  
} 

Output

The maximum Element in the heap is: 10
The Maximum Element after removing the previous max in the heap is: 9

Complexity Analysis

Time Complexity

Since for a k-ary heap, the maximum height of the heap will be logkn, where n is the number of elements in a heap. 

  1. For insertion, we do heapify upwards, and since the maximum height of the heap can be logkn, the time complexity for inserting a value in a heap is O(logkn), where n = number of elements in the heap.
  2. Time Complexity for fetching the maximum element is O(1).
  3. For removing the max element, we do downward heapification, and since the maximum height of the heap can be logkn. At each level, we compare all the k children of the node with the parent, the time complexity for removing the max element from the heap is O(k*logkn) where n = number of elements in the heap.

Space Complexity

Since we are maintaining an array to store the elements of the heap, space complexity is O(n), where n = the total number of elements in the heap.


Check out this problem - Largest BST In Binary Tree

Also Read, Prefix Sum Array

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is the difference between a tree and a graph?

Trees and graphs are different since there can never be loops in a tree, but we can have loops in a graph. Also, all the nodes in a tree are always connected, but that is not true for a graph.

What is a priority queue?

Every value has some priority associated with it in a priority queue, and the value with the highest priority is dequeued first.

What is the difference between heapify up and heapify down?

When adding a new element to a heap, we do upward heapification. When we add a new element to the heap, we insert it at the bottom and move up the tree, comparing it to the current parent element and swapping if the parent is smaller (in the case of a max heap).
Whereas when we remove the top element from a heap, we use heapify down. When an element from a heap is removed, the top element is swapped with the last element at the bottom of the tree, the last element is removed, and the new top element is heapified down to keep the heap property.

What are the applications of N-ary heaps?

1. Since the time of insertion in n-ary heaps is O(logkn), whereas in binary heaps is O(log2n). Therefore insertion operation is faster in an n-ary heap than the binary heap. But since the operation of removing the maximum element from the n-ary heaps (O(k*logkn)) is slower as compared to removing the maximum element in a binary heap (O(logkn)). Therefore n-ary heap is used when insertion operations are more frequently used than the remove operation.
2. N-ary heap has better memory cache behaviour as compared to a binary heap.

Conclusion

In this article, we learned about n-ary heaps in detail. We learned how they are implemented and what their applications are.

Since heap data structure is frequently asked in interviews, we recommend you practice problems based on heaps on Coding Ninjas Studio. 

Recommended Readings:


Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass