![1. Suppose that an array al] is a max-heap that contains the distinct integer keys 1, 2,.., N with N> 7. The key N must be in gl1] and the key N-1 must be in either al2) or al3) a. Give all possible positions for the key N-2 as a function of N. b. Repeat the same question for the key 2](http://img.homeworklib.com/questions/885750c0-c745-11eb-8b78-c9bf9e15c553.png?x-oss-process=image/resize,w_560)
Homework Answers
a.
The possible position of key N-2 if N> 7 is in either at level 1 or level 2.
At level 0, only N could be possible.
So the possible position of key N-2 is a[2],a[3],a[4],a[5],a[6],a[7] which is independent of N
All the red nodes in foll. diagram are possible position of key N-2.
b. The possible position of 2 is either the leaf node or the parent of last node if N is even and value of last node is 1.
Any other position is not possible because if no. of children is two, key of the node must be greater than 2.
So, if N is odd, possible position of key 2 is a[(N+1)/2],a[(N+1)/2 + 1], ......... a[N]
and if N is even, possible position of key 2 is a[N/2],a[N/2 + 1], ......... a[N].
Diagram of this is not possible to draw.
Add Answer to:
1. Suppose that an array al] is a max-heap that contains the distinct integer keys 1,...
Using C++, data structures, C++ STL, inputs and expected outputs are shown below. Max Heap Heap...
Using C++, data structures, C++ STL, inputs and expected
outputs are shown below.
Max Heap Heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either > (in a max heap) or s (in a min heap) the key of C. The node at the "top" of the heap (with no parents) is called the root node. In binary-tree based heap, it...
Consider the following max-heap stored as an array: <7, 6, 4, 2, 5, 1, 3>. Draw...
Consider the following max-heap stored as an array: <7, 6, 4, 2, 5, 1, 3>. Draw this max-heap as an (undirected) binary tree and give both adjacency-list representation and adjacency-matrix representation of the binary tree
1. In Lab 4, you developed a program to build a Max Heap, and then Heap...
1. In Lab 4, you developed a program to build a Max Heap, and then Heap Sort. Update the program by adding two additional functions: (a) AddData(A, N, V) where V is the new value added. (b) Delete a data Delete by giving the index of the data position Make sure to display the array after calling each of the function. 2. Write a program to implement Binary Search Algorithm, which will return the index of the data searched (V)....
5. A three-heap with n elements can be stored in an array A, where A[O] contains...
5. A three-heap with n elements can be stored in an array A, where A[O] contains the root of the tree. a) Draw the three-heap that results from inserting 5, 2, 8, 3, 6, 4, 9, 7, 1 in that order into an initially empty three-heap. You do not need to show the array representation of the heap. You are only required to show the final tree, although if you draw intermediate trees. b) Assuming that elements are placed in...
Suppose we have an array that contains tuples. These tuple contains three positive numbers. Implement an...
Suppose we have an array that contains tuples. These tuple contains three positive numbers. Implement an algorithm that counts how many distinct tuple that an array has(contains same number in same order). ex) [(1, 2, 1), (2, 2, 2), (3, 8, 3), (1, 2, 1), (3, 4, 3)] gives 4. 1 The algorithm should be implemented in Python3. 2 The function must have average-case runtime of O(n). You can assume Simple Uniform Random Hashing. 3 Python built-in dictionary cannot be...
4 Easy Quiz Questions Question 1: Below are the contents of the id array for the...
4 Easy Quiz Questions Question 1: Below are the contents of the id array for the quick-find version of the Union-Find algorithm. 0,4,7,0,4,4,4,7,8,0 The contents are listed in order from slot 0 to slot 9. (So for example, id[1] is 4 and id[2] is 7. What are the contents of the id array after the call union(5, 3)? Use the same format as above (a comma-separated listing of the contents without spaces). _____________________ Question 2 Below are the contents of...
#include <stdio.h> // Define other functions here to process the filled array: average, max, min, sort,...
#include <stdio.h>
// Define other functions here to process the filled array: average, max, min, sort, search
// Define computeAvg here
// Define findMax here
// Define findMin here
// Define selectionSort here ( copy from zyBooks 11.6.1 )
// Define binarySearch here
int main(void) {
// Declare variables
FILE* inFile = NULL; // File pointer
int singleNum; // Data value read from file
int valuesRead; // Number of data values read in by fscanf
int counter=0; // Counter of...
PROGRAM DESCRIPTION Using the given class definitions for either C++, create a minimum heap that stores...
PROGRAM DESCRIPTION Using the given class definitions for either C++, create a minimum heap that stores integers and and implements a minimum priority queue. (Your program can be "hard coded" for integers - it does not need to use templates, generics, or polymorphism.) Your data structure must always store its internal data as a heap. Your toString function should return a string with the heap values as a comma separated list, also including the size of the heap as well....
Question 6: Let n 2 1 be an integer and let A[1...n] be an array that...
Question 6: Let n 2 1 be an integer and let A[1...n] be an array that stores a permutation of the set { 1, 2, . .. , n). If the array A s sorted. then Ak] = k for k = 1.2. .., n and, thus. TL k-1 If the array A is not sorted and Ak-i, where iメk, then Ak-서 is equal to the "distance" that the valuei must move in order to make the array sorted. Thus,...
Please finish all the questions,Thanks Following is Appendix assume the definition of Java class Heap given in the App...
Please finish all the questions,Thanks
Following is Appendix
assume the definition of Java class Heap given in the Appendix For this question, a. (2 marks Consider the following heap 30 12 20 19 6 10 18 Given the array representation of a heap discussed in class, what is the array that corre sponds to this heap? b. (5 marks) Successively insert into the heap of part (a.) 22, 35 and 11, in that order. Use the standard heap insertion algorithm....
Using C++, data structures, C++ STL, inputs and expected
outputs are shown below.
Max Heap Heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either > (in a max heap) or s (in a min heap) the key of C. The node at the "top" of the heap (with no parents) is called the root node. In binary-tree based heap, it...
1. In Lab 4, you developed a program to build a Max Heap, and then Heap Sort. Update the program by adding two additional functions: (a) AddData(A, N, V) where V is the new value added. (b) Delete a data Delete by giving the index of the data position Make sure to display the array after calling each of the function. 2. Write a program to implement Binary Search Algorithm, which will return the index of the data searched (V)....
5. A three-heap with n elements can be stored in an array A, where A[O] contains the root of the tree. a) Draw the three-heap that results from inserting 5, 2, 8, 3, 6, 4, 9, 7, 1 in that order into an initially empty three-heap. You do not need to show the array representation of the heap. You are only required to show the final tree, although if you draw intermediate trees. b) Assuming that elements are placed in...
#include <stdio.h>
// Define other functions here to process the filled array: average, max, min, sort, search
// Define computeAvg here
// Define findMax here
// Define findMin here
// Define selectionSort here ( copy from zyBooks 11.6.1 )
// Define binarySearch here
int main(void) {
// Declare variables
FILE* inFile = NULL; // File pointer
int singleNum; // Data value read from file
int valuesRead; // Number of data values read in by fscanf
int counter=0; // Counter of...
Question 6: Let n 2 1 be an integer and let A[1...n] be an array that stores a permutation of the set { 1, 2, . .. , n). If the array A s sorted. then Ak] = k for k = 1.2. .., n and, thus. TL k-1 If the array A is not sorted and Ak-i, where iメk, then Ak-서 is equal to the "distance" that the valuei must move in order to make the array sorted. Thus,...
Please finish all the questions,Thanks
Following is Appendix
assume the definition of Java class Heap given in the Appendix For this question, a. (2 marks Consider the following heap 30 12 20 19 6 10 18 Given the array representation of a heap discussed in class, what is the array that corre sponds to this heap? b. (5 marks) Successively insert into the heap of part (a.) 22, 35 and 11, in that order. Use the standard heap insertion algorithm....
Most questions answered within 3 hours.
-
Lowell Corp. sells $100,000 of bonds to private investors. The
bonds are due in five years,...
asked 40 minutes ago -
3) Do you believe that Disney’s
acquisition-based growth strategy is sustainable?
4) Which competencies support this...
asked 57 minutes ago -
Rank the following three stocks by their total risk level highest
to lowest night writer has...
asked 1 hour ago -
A local
electronic company primarily manufactures four highly technical
telecommunication products. Each product must be processed...
asked 2 hours ago -
•Describe the basic structure of collagen monomers •Explain how
amino acid composition of collagen contributes to...
asked 4 hours ago -
Compute the sample correlation coefficient
r for each of the following data sets.
(Use 3 decimal...
asked 4 hours ago -
5a. What are the advantages and disadvantages of Proxy ARP?
b. What is the TTL field...
asked 4 hours ago -
An ice cube (density = 900[kg/m3]) with a side length of
2.54[cm] is held by a...
asked 6 hours ago -
would you say that leaders in the international context are born
or made? That is, can...
asked 6 hours ago -
Instructions
Read the Digital Trends article "Solid state drives are speedier
than hard disk drives. Are...
asked 6 hours ago -
A multiple-choice test consists of 29 questions with possible
answers of a, b, c, d. Estimate...
asked 6 hours ago -
Question 1: Ethanol is the active ingredient of alcoholic
beverages. It is also s a possible...
asked 6 hours ago