A trinary heap is a heap in which each node has up to 3 children (a left child,

Question

A trinary heap is a heap in which each node has up to 3 children (a left child, a center child, and a right child). Since it's a heap, each level of the heap must be filled before a new level is started, and each partially-full level of the heap must be filled left to right. For example, here is a trinary min-heap containing 12 numbers: 19 18 14 37 20 A common way of working with binary heaps is to store them in an array. In this case, the 0-th element of the array is the head, and for the element at index j its two children are at indices 2/+1 and 2/+2. For example, here's a binary heap and an array that would store it 14 19 20 18 Index 2 4 5 Value 2 4 20 18 30 Part A:15 pts] You can also store trinary heaps in an array using the same idea as the above idea for binary heaps. For a trinary heap, if an element of the heap is stored at index k, what are the indices of its 3 children

Explanation / Answer

ANSWER

PART (A) :

If a element is stored at location k its children are at indices (k*3)+1 , (k*3)+2 , (k*3)+3

So, for n children heap if a element is stored at k its children will be stored at :

(n*k)+1, (n*k)+2, (n*k)+3, (n*k)+4, ....,(n*k)+n

In our case n = 3 .

So, children are at indices (3*k)+1 , (3*k)+2 , (3*k)+3

EXTRA INFO : So the parent of element at position k in a trinary heap is at position (k-1)/3

PART (B) :

Psedocode for MaxHeapify() for trinary heap :

Max-Heapify(A, i)

lf Left(i)
rt Right(i)
ct Center(i)
if lf heap-size[A] and A[lf] > A[i]
then largest l
else largest i
if rt heap-size[A] and A[rt] > A[largest]
then largest rt
if ct heap-size[A] and A[ct] > A[largest]
then largest ct
if largest not equal i
then exchange A[i] A[largest]
Max-Heapify(A, largest)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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