please write the algorithm for the following propblem and explain your answer. I

Question

please write the algorithm for the following propblem and explain your answer.

In section 5.7 we defined heaps in terms of an essentially completely binary tree. It should be clear that the idea can be generalized to essentially complete K-ary trees, for any k 2. Show that we can map the nodes of a K-ary tree containing n nodes to the elements T[0] to T [n-1] of an array in such a way that the parent of the node represented i T[i] is found in T[(i-1) K] for i>0, and the children of the node represented in T[i] are found in

Explanation / Answer

Answer for Question:

Pseudo code for Given problem:

The two most important heap algorithms are sift-down and percolate. Master these and you've nearly mastered heaps.

procedure sift-down( T[1..n], i )
k = i
repeat
j = k
if 2j <= n and T[2j] > T[k] then k = 2j
if 2j < n and T[2j+1] > T[k] then k = 2j + 1
exchange T[j] and T[k]
until j == k
  
  

procedure percolate( T[1..n], i )
k = i
repeat
j = k
if j > 1 and T[j div 2] < T[k] then k = j div 2
exchange T[j] and T[k]
until j == k
  
Advantages of Generalised heaps:

-easy implementation
-for small d2d2 we get a more cache-efficient data structure then a binary heap
-large dd's are preferable for external data structures where the number of disk accesses should be minimized

Disadvantages:

two heaps cannot be easily merged

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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