A d-ary heap is like a binary heap, but (with one possible exception) non-leaf n

Question

A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children. (Note: don’t not assume d is constant.)

How would you represent a d-ary heap in an array? (write down explicitly how to find the index of a node’s parent, and i-th child).

What is the height of a d-ary heap of n elements in terms of n and d?

Give an efficient algorithm (pseudocode needed) of deleting the maximum value in d-ary max-heap.

State the running time in terms of d and n.

Explanation / Answer

A)

The following expressions determine the parent and j-th child of element i (where 1 j d): Parent(i) = $ i + d 2 d % , Child(i, j)=(i 1) · d + j + 1.

B)

The Heapify algorithm is somewhat different from the binary-heap version, whereas HeapInsert is identical to the corresponding algorithm for binary heaps. The running time of

Heapify is O(d · logd n), and the running time of Heap-Insert is O(logd n).

Heapify(A, i, n, d)

largest i

for l Child(i, 1) to Child(i, d) loop through all children of i

do if l n and A[l] > A[largest]

then largest l

if largest 6= i

then exchange A[i] A[largest] Heapify(A, largest)

Heap-Insert(A, key)

heap-size[A] heap-size[A]+1

i heap-size[A]

while i > 1 and A[Parent(i)] < key

do A[i] A[Parent(i)]

i Parent(i)

A[i] key

C)

The height h of a heap is approximately equal to logd n. The exact height is

h = dlogd(n · d n + 1) 1e.

// RATE MY ANSWERS

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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