In Section 5.7 we defined heaps in terms of an essentially complete binary tree.

Question

In Section 5.7 we defined heaps in terms of an essentially complete binary tree. It should be clear that the idea can be generalized to essentially complete binary trees, for any k> 2. Show that we can map the nodes of a binary tree containing n nodes to the elements 0] to 1] of an array in such a way that the parent of the node represented in T[i] is found in T[(i - l)+k]for i > 0, and the children of the node represented in T[t] are found in T[ik + 1], T[ik +2T[(i+ 1)k].Note that for binary trees, this is not the mapping we used in Section 5.7; there we used a mapping onto T[l..n], not onto T[0..n -1]. Write procedures sift-down(T, k, i) and percolate (k, i) for these generalized heaps. What are the advantages and disadvantages of such generalized heaps? For an application where they may be useful, see Problem 6.16.

Explanation / Answer

procedures sift-down (T, k, i) and percolate (T, k, i)

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

procedure percolate( T, k,i )
    k = i
    repeat
        ik = k
        if ik > 1 and T[ik div 2] < T[k] then k = ik div 2
        exchange T[ik] and T[k]
    until ik == k

Advantage

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

Disadvantage

1- Two heaps cannot be easily merged

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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