Problem 5.23. (k-ary heaps) In Section 5.7 we defined heaps in terms of an essen
ID: 3677317 • Letter: P
Question
Problem 5.23. (k-ary heaps) 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 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 in 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 T[ik + 1], T[ik + 2],..., T[(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[1...n], not onto T[O..n -1]. Write procedures sift-down (T, k, i) and percolate (T, k, i) for these generalized heaps. What are the advantages and disadvantages of such generalized heaps? Problem 5.23. (k-ary heaps) 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 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 in 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 T[ik + 1], T[ik + 2],..., T[(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[1...n], not onto T[O..n -1]. Write procedures sift-down (T, k, i) and percolate (T, k, i) for these generalized heaps. What are the advantages and disadvantages of such generalized heaps? Problem 5.23. (k-ary heaps) 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 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 in 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 T[ik + 1], T[ik + 2],..., T[(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[1...n], not onto T[O..n -1]. Write procedures sift-down (T, k, i) and percolate (T, k, i) for these generalized heaps. What are the advantages and disadvantages of such generalized heaps?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
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