Num #7 You have a correctly implemented Max-Heap class (indices starting at 1),

Question

Num #7

You have a correctly implemented Max-Heap class (indices starting at 1), which provides the two following helper functions (in addition to insert, remove, peek): (a) trickleUp (int i) (David's lecture) a.k.a. insert (int i) (Mark's lecture) takes the element at position i and b) trickleDown (int i) (David's lecture) a.k.a. heapify (int i) (Mark's lecture) takes the element at position keeps swapping it with its parent (and grandparent etc.) until it is no larger than the parent at the time. i and keeps swapping it with the larger of its children (and grandchildren etc.) until it is no smaller than both children Suppose that you get an instance whose array elements are not in correct heap order, i.e., the heap property does not hold yet. You want to establish the correct arrangement, by using the two helper functions given above. Which of the following two alternatives do this correctly? Explain why they are correct or incorrect. For incorrect ones, give an example of an initial heap which is not correctly processed, and explain what happens when the incorrect variant is executed on it Heap h; // Variant 1 for (int í = 1; ?

Explanation / Answer

Suppose we have an array of elements that are not in the correct heap order. In that case we apply the heapify or the trickleDown function to build the heap or to arrange the elements correctly. We apply the heapify or the trickleDown function on all the non leaf nodes.

We cannot use the trickleUp function because it works when you want to insert a single element into the heap at the correct position. However for arranging multiple elements, tricleUp will not work since after one element has been inserted into its proper position by trickleUp, when we operate on another element, it can break the arrangement of the previous element so you again need to arrange the first element into its proper position.

For example , lets take 4, 10, 3, 5, 1 and we build a max heap from this array.

Let us consider usying trickle Up.

For 5 and 1, we donot need to swap as 10 is already greater than 5 and 1.

For , 10 , we swap it with 4 and the array becomes 10 4 3 5 1. This in turn breaks the arrangement of 5 and 1 as now , the parent of 5 and 1 which is 4 is smaller than 5. Thus we have already looped through 5 but its arrangement is broken and hence this method is not useful.

If we use trickleDown approach on 4, 10, 3, 5, 1,

Let us consider 4. First we swap 4 and 10 , then we get 10 4 3 5 1 and then we swap 4 and 5 and we get the heap as 10 5 3 4 1.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.