Question

In heapsort we view an array as a binary tree using the following mapping: a[0] is...

In heapsort we view an array as a binary tree using the following mapping: a[0] is the root of the entire tree and for element a[i], its left child is a[2i+1] and its right child is a[2i+2]. Answer the following questions for an array of size n. ( Answers in some cases may be in terms of n.)

a) What is the index of the parent a[i] for any i > 0?

b) What is the biggest index for which a[i] is not a leaf?

c) What is the smallest value of i for which a[i] is a leaf?

d) Suppose n is one billion. What is the exact height of the tree? (height = maximum path length root to some leaf, path length = # of nodes)

Homework Answers

Answer #1

Here we take inital index as zero for all.

a) The formula to calculate index of the parent a[i] for any i>0 is : floor((i-1)/2)

b) The formula to calculate  the biggest index for which a[i] is not a leaf is : floor(n/2)-1

c) The formula to calculate  the smallest value of i for which a[i] is a leaf is : floor(n/2)

d) One billionn = 10^9 = N

formula for height of a complete binary tree (if root is not count in height)=> ceil(log 2(N+1))-1 [ log 2 mean log base 2]

=>ceil(log2(1000000000+1))-1

=>ceil(29.8973)-1 => 30-1 => 29

if root is count in height => ceil(log2(N+1)) [log 2 means log base 2]

=> 30

  

Generally ,root is not count in height as per wikipedia.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
A binary tree isfullif every non-leaf node has exactly two children. For context, recallthat we saw...
A binary tree isfullif every non-leaf node has exactly two children. For context, recallthat we saw in lecture that a binary tree of heighthcan have at most 2h+1−1 nodes, and thatit achieves this maximum if it iscomplete, meaning that it is full and all leaves are at the samedistance from the root. Findμ(h), theminimumnumber of nodes that a full tree of heighthcan have, and prove your answer using ordinary induction onh. Note that tree of height of 0 isa single...
For this question, consider the following class which will be used to construct binary trees. Use...
For this question, consider the following class which will be used to construct binary trees. Use the convention that there is no "empty tree"; each node points to the nodes containing it's two children; and if a node has no left or right child, then the corresponding pointer will be set to null public class TreeNode { public double root; public TreeNode left; public TreeNode right; } Draw a diagram for what a tree of this model would look like...
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class is empty. Complete the destructor so the memory allocated for each node in the BST is freed. Make a couple of different trees in your main method or in a function to test the destructor (the program should not crash upon exiting). bst.zip (includes the following files below in c++): bst.h: #pragma once #include #include "node.cpp" using namespace std; template class BST { public:...
import java.util.ArrayList; /* Rules:         1. Allow Tester to iterate through all nodes using the...
import java.util.ArrayList; /* Rules:         1. Allow Tester to iterate through all nodes using the in-order traversal as the default.             This means, in Tester the following code should work for an instance of this class             called bst that is storing Student objects for the data:                 BinarySearchTree_Lab08<String> bst = new BinarySearchTree_Lab08<String>();                 bst.add("Man");       bst.add("Soda");   bst.add("Flag");                 bst.add("Home");   bst.add("Today");   bst.add("Jack");                ...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted below) Implement the following methods using recursion: int depth() // returns the length of the deepest path from root to any leaf int node_count() // returns the number of nodes in the tree void insert(int n) // inserts value n into the tree BinarySearchTree2C clone() // returns a clone (deep copy) of the tree Add code to the main method to test these methods....
CRYPTOGRAPHY PROBABILITY DISTRIBUTION Bad Shuffles Consider the following card shuffling algorithm. There are three cards in...
CRYPTOGRAPHY PROBABILITY DISTRIBUTION Bad Shuffles Consider the following card shuffling algorithm. There are three cards in the deck and they are each represented by an element in {X, Y, Z}. [Bonus marks if you use the deck {W, X, Y, Z}] Algorithm Shuffle --------------------------------------------------- deck := [X,Y,Z] for i from 0 to 2 do j := RANDOM(i) swap values of deck[i] and deck[j] end for return deck --------------------------------------------------- For each of the following definitions of RANDOM(i), compute the probability distribution...
Copy the file SimplerBST.java from the week 1 examples package and rename the file and class...
Copy the file SimplerBST.java from the week 1 examples package and rename the file and class A3BST. Add two public methods: one named countTwins that takes no parameters and that, when called, traverses every node of the tree to count the number of nodes having two children. one named lessThanValueCount that takes a paremeter of generic type V, and that, when called, traverses every node of the tree to count the number of nodes whose value (not its key) is...
This laboratory assignment involves implementing a data structure called a map. A map associates objects called...
This laboratory assignment involves implementing a data structure called a map. A map associates objects called keys with other objects called values. It is implemented as a Java class that uses arrays internally. 1. Theory. A map is a set of key-value pairs. Each key is said to be associated with its corresponding value, so there is at most one pair in the set with a given key. You can perform the following operations on maps. You can test if...
Hi, I am trying to create an XML JTree viewer using the DOM parser instead of...
Hi, I am trying to create an XML JTree viewer using the DOM parser instead of the SAX parser, I am having trouble changing my code in order to utilize the DOM parser to extract the XML data into the tree structure. Would you be able to explain what changes should be made to the code in order to use the DOM parser instead of the SAX parser? // Java Packages //      import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.io.File; import...