Question

Assume that a max-heap with 10^5 elements is stored in a complete 5-ary tree. Approximately how many comparisons a call to Insert() will make?

Answer 1

Answer: 7

Explanation: A max heap is a tree with every node capable of having maximum 5 children and full(meaning the leaves are all in the same level and full by left to right)

Now in such a tree with n elements will have the height of log(n). If you can't visualize this think of a binary heap with root at level 0, having 3 levels and only one node in the level 3. that means there are 8 elements. Now calculate the height, i.e floor(log(n)) =>log8 (log base 2 since binary tree)

-> 3 is the height of the binary heap

This means you will have to make atleast 3 comparisons when you try to insert a node into this binary heap.

In the same way for an 5-ary heap with $10^{5}$ elements it would take floor(log($10^{5}$))

(log base 5 since 5-ary tree).

i.e 5 log10=5*1.43=floor(7.15)=7

This means you will have to make atleast 7 comparisons when you try to insert a node into this 5-ary heap with $10^{5}$ elements .