Algorithm Please answer and write it clearly thanks A d-ary heap is like the bin

Question

Algorithm

Please answer and write it clearly

thanks

A d-ary heap is like the binary heaps that we studied in class, except that the corresponding heap structure is a d-ary tree (d > 2) rather than a binary tree. Heapsort can be implemented using a d-ary heap in much the same way that we implemented heapsort using a binary heap. We may refer to such heapsort algorithms as d-ary heapsort and binary heapsort respectively. Circle one, and justify your answer on the back of this page "If the functions T_2(N) and T_d(N) give the worst-case running times (as a function of the number N of elements in the array being sorted) of a binary heapsort and a d-ary heapsort respectively, then T_2(N) and T_d(N) lie in different Theta classes."

Explanation / Answer

HEAPSORT (A)

Running time analysis:

1. Build_Heap takes (n) time

2. Heapify takes ((d-1) lgd(n) ) and is run for n-1 elements.(this is the worst case run time of heapify. in the worst case, an element would move through all levels of tree (lgd(n) is the number of levels) and there would be d-1 comparisons at each level).

So Total runtime for d-ary heap = (n) + ( (d-1) lgd(n) )* n-1

                                                        = (n) + ( (d-1)(n-1) lgd(n))

                                                        = (n) + d ( n lgd(n))    (d is a constant) = ( n lgd(n))

For Binary heap, worst case running time becomes ( n lg2(n)) which is equal to ( n log(n)).

Please let me know in case of any doubts.

Thanks

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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