Question

The smallest item in a heap (assume min-heap) must appear in position 0, and the second...

  1. The smallest item in a heap (assume min-heap) must appear in position 0, and the second smallest must be in position 1 or position 2.

    (a) (3 points) Give the list of positions in a heap where the third smallest can appear. (b) (3 points) Give a list of positions where the fourth smallest can appear.

Homework Answers

Answer #1

(a) List of positions in a heap where the third smallest can appear is 1,2,3,4,5 and 6.

(b) List of positions where the fourth smallest can appear is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 and 14.

For example:

In the given graph the deepest level where 3rd smallest element can occur is 3 (element 2).

In the given graph the deepest level where 4th smallest element can occur is 4 (element 3).

So we can see that at maximum the 3rd smallest element require positions atmost upto 3rd level and 4th smallest element require positions atmost upto 4th level.

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
For this problem, assume k = 1 (in the appropriate units of 1/min or m3/min-mol for...
For this problem, assume k = 1 (in the appropriate units of 1/min or m3/min-mol for the case being analyzed), FAo = 1 mol/min and vo= 1 m3/min. a.Compare quantitative Levenspiel plots (1/r vs fA and 1/r vs CA, as you may guess both axes must start at 0, and fA can only vary from 0 to 1) for the reaction A→B with kinetics r = kCA and 2A→B with kinetics r = kCA2 (4 plots total here). Which reactor...
Must use loops. Please do not use sequence of if statements. I need it in C++....
Must use loops. Please do not use sequence of if statements. I need it in C++. Given 2 strings, a and b, set result to the number of the positions where they contain the same length 2 substring. So "xxcaazz" and "xxbaaz" yields 3, since the "xx", "aa", and "az" substrings appear in the same place in both strings. for input of "xxcaazz", "xxbaaz" → 3 for input of "abc", "abc" → 2 for input of "abc", "axc" → 0
Three +2 µC point charges are fixed in space in the following locations: the first at...
Three +2 µC point charges are fixed in space in the following locations: the first at <1, 0, 0> cm, second at <0, 2, 0> cm, and a third at <-4, 0, 0> cm. (a) Find the net electric field at positions <0, 0, 0> cm and <-1, 1, 0> cm. (b) For each location where you found the electric field, what is the force on a -3 µC test charge.
Consider the following string of page references: 7, 0, 1, 2, 0, 3, 0, 4, 2,...
Consider the following string of page references: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. The main memory can only contain THREE frames. Show the frame allocation for: (60 points) FIFO (First-in-First-out) LRU (Least Recently Used) Clock Optimal (assume the page reference string continues with 1, 2, 0, 1, 7, 0, 1) List the total number of page faults and the miss rate for each policy. Count page faults only after all frames have been...
1. What must have been true of T-Mobile's position on its long-run average cost curve for...
1. What must have been true of T-Mobile's position on its long-run average cost curve for providing wireless services (especially 5G based) if it expected to benefit from buying Sprint? 2. Draw a long-run average cost curve for T-Mobile to illustrate the firm's position on the curve before the merger. Be sure to label your graph properly (title, axes, curves, positions, etc.). Your graph should be "stand-alone" which means a reader can easily interpret your graph. 3. In your graph,...
Create a C++ project. Download and add the attached .h and .cpp to the project. Write...
Create a C++ project. Download and add the attached .h and .cpp to the project. Write an implementation file to implement the namespace declared in the attached CSCI361Proj5.h. Name the implementation file as YourNameProj5.cpp and add it to the project. Run the project to see your grade. .h file: // Provided by: ____________(your name here)__________ // Email Address: ____________(your email address here)________ // FILE: link.h // PROVIDES: A toolkit of 14 functions for manipulating linked lists. Each // node of...
in C++ Please and thanks Here is a list of 6 numbers. Use the selection sort...
in C++ Please and thanks Here is a list of 6 numbers. Use the selection sort algorithm to sort this list. Fill in this table with each iteration of the loop in the selection sort algorithm. Mark the place from which you are looking for the 'next smallest element'. In this display, the upper numbers are the indices, the lower numbers are in the corresponding positions. Use the several rows provided to show the sequence of steps. 0 1 2...
A python question... In your class, many students are friends. Let’s assume that two students sharing...
A python question... In your class, many students are friends. Let’s assume that two students sharing a friend must be friends themselves; in other words, if students 0 and 1 are friends and students 1 and 2 are friends, then students 0 and 2 must be friends. Using this rule, we can partition the students into circles of friends. To do this, implement a function networks() that takes two input arguments. The first is the number n of students in...
Consider the nonlinear second-order differential equation 4x"+4x'+2(k^2)(x^2)− 1/2 =0, where k > 0 is a constant....
Consider the nonlinear second-order differential equation 4x"+4x'+2(k^2)(x^2)− 1/2 =0, where k > 0 is a constant. Answer to the following questions. (a) Show that there is no periodic solution in a simply connected region R={(x,y) ∈ R2 | x <0}. (Hint: Use the corollary to Theorem 11.5.1>> If symply connected region R either contains no critical points of plane autonomous system or contains a single saddle point, then there are no periodic solutions. ) (b) Derive a plane autonomous system...
By JAVA programming language public void expand(Object a) {     // assume element has enough capacity...
By JAVA programming language public void expand(Object a) {     // assume element has enough capacity     for (int i = size - 1; i >= 0; i--) {         element[4 * i + 3] = a;         element[4 * i + 2] = a;         element[4 * i + 1] = a;         element[4 * i] = element[i];      }      size = 4 * size; } element is a one-dimensional array that stores elements of the type Object....