Answer to Question #230344 in Java | JSP | JSF for Anonymous

Question

1: In a N-ary land, people really like the number ‘n’. You are their chief algorithms

expert and given the task of designing an n-ary heap for these people. An n-ary heap is

like a binary heap, but non-leaf nodes have ‘n’ children instead of

2 children. You have to design an n-ary heap and answer the following

a) How can we represent an n-ary heap in an array?

b) Let’s say we have an n-ary heap which contains ‘d’ number of elements in total. Give the

height of this heap in terms of ‘n’ and ‘d’.

c) Give an efficient implementation of EXTRACT-MAX and INSERT in an n-ary Max heap.

Analyse the running times of both of the functions in terms of ‘d’ (total size) and n.

d) Give an efficient implementation of DECREASE-KEY(A, i, k) which will give an error if k

> A[i], but otherwise sets A[i] = k and then updates the n-ary max-heap structure

appropriately. Analyse its running time in terms of ‘d’ (size) and n.

Answer 1

import java.util.*;
 
class Main
{
 
static class Node
{
    char k;
    Vector<Node > c;
};


static Node newNode(int k)
{
    Node tmp = new Node();
    tmp.k = (char) k;
    tmp.c = new Vector<Node>();
    return tmp;
}
 
static int depth_of_tree(Node p)
{
   
    if (p == null)
        return 0;
    int max_depth = 0;
    for (Node t : p.c)
        max_depth = Math.max(max_depth,
                            depth_of_tree(t));
 
    return max_depth + 1 ;
}


public static void main(String[] args)
{
     
    Node r = newNode('A');
    (r.c).add(newNode('B'));
    (r.c).add(newNode('F'));
    (r.c).add(newNode('D'));
    (r.c).add(newNode('E'));
    (r.c.get(0).c).add(newNode('K'));
    (r.c.get(0).c).add(newNode('J'));
    (r.c.get(2).c).add(newNode('G'));
    (r.c.get(3).c).add(newNode('C'));
    (r.c.get(3).c).add(newNode('H'));
    (r.c.get(3).c).add(newNode('I'));
    (r.c.get(0).c.get(0).c).add(newNode('N'));
    (r.c.get(0).c.get(0).c).add(newNode('M'));
    (r.c.get(3).c.get(2).c).add(newNode('L'));
     
    System.out.print(depth_of_tree(r) + "\n");
}
}