Consider a min-heap complete tree consisting of 5000 nodes. a) What is the exact

Question

Consider a min-heap complete tree consisting of 5000 nodes. a) What is the exact height of this tree? b) How many nodes are at the deepest level? c) How many nodes are at the second deepest level? d) How many swaps, in the worst case, are required in order to insert a new element in this tree? Explain. tree? Explain. the worst case, will be needed? e) How many swaps, in the best case, are required in order to insert a new element in this f) If you want to check if element 10000 is present in this heap, how many comparisons, in

Explanation / Answer

a) Heightif this tree...
height = log(base2)(n+1)-1 ===> log2(5001) - 1 ====> 13 - 1 ===> 12

b) nodes at deepest level
Formula is 2^(h+1) - 1
==> deepest level is 12
So 2^13 - 1 ===> 8192 - 1 ===> 8191

c)
Nodes at second deepest level
Formula is 2^(h+1) - 1
==> deepest level is 12, second deepest 11
So 2^12 - 1 ===> 4096 - 1 ===> 4095

d)
Worst case to insert a new node required swaps are O(n) ==> n comparisions ==> 5000 comparisions

e)
Best case to insert a new node required swaps are O(log n) ===> log 5000 ===> 3.69 ~~ ===> 4 swaps

f)
In binary heap, every step we will lef with half comparisions..
so half of elements will reduce from first step ... and goes on..
It will be equal to log2 (n) ===> log2 (10000) ===> 13.28 ===> 14 comparisions needed.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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