A d-ary max-heap, d-heap for short, is the generalization of a binary heap to a

Question

A d-ary max-heap, d-heap for short, is the generalization of a binary heap to a d-ary tree, for a fixed d greaterthanorequalto 2. Every node can have up to d children, the tree has to be almost complete, and the max-heap property is fulfilled. (a) For given fixed h greaterthanorequalto 0 and d greaterthanorequalto 2, give a formula for the number n of nodes in a complete d-ary tree of height h. Your formula should depend on n and d. Justify its correctness. (b) Suppose a d-heap is stored in an array that begins with index 0. For an entry located at index i, in which location is its parent and in which locations are its children? (No formal proof necessary.) (c) What is the height of a d-heap that contains n elements? The height should be a function of n and d. Shortly justify your answer: a formal proof is not necessary. (d) Shortly explain how the insertion procedure works for d-heaps (you do not have to give pseudocode). What is the runtime of inserting an element into a d-heap of n elements? The runtime should be a function of n and d. (e) Shortly explain how the extract_max procedure works for d-heaps (you do not have to give pseudocode). What is the runtime in terms of n and d, where n is the number of elements in the heap?

Explanation / Answer

1.A D-array will have a height of=theta(logn/logb)

as we know 1+d+d^2+d^3+.......................+d^(h-1)<n<=1+d+d^2+d^3+.......................+d^h

d^(h-1)/d-1<=d^(h+1)-1/d-1

d^h<n(d-1)+1<=d^(h+1)

h< logd(n(d-1)+1)<=h+1

2.parent[i]=floor((i-1)/d)

jth child[i]=d*i+j

3.A D-array will have a height of=logn/logb

as we know 1+d+d^2+d^3+.......................+d^(h-1)<n<=1+d+d^2+d^3+.......................+d^h

d^(h-1)/d-1<=d^(h+1)-1/d-1

d^h<n(d-1)+1<=d^(h+1)

h< logd(n(d-1)+1)<=h+1

4.Insert(Array,key,n,d)

n=n+1

A[n]=-inf

Increase_Key(Array,i,key,n)

runtime=log n/log d

5.Extract_Max(Array,n)

max=Array[n]

Array[1]=Array[n]

n--

Heapify(A,1,n,d)

return max;

runtimw=Big O(d*logd n)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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