1. (k-ary min-heaps) A k-ary heap is like a binary heap, except that non-leaf no
ID: 3800253 • Letter: 1
Question
1. (k-ary min-heaps) A k-ary heap is like a binary heap, except that non-leaf nodes have k
children (except possibly for one node that can have fewer children). Like binary heaps, k-aryheaps can be stored in an array (in layers, starting from the root).
In this problem, you will implement k-ary heaps (on Vocareum). You will have to supportinsertion and extraction. Unlike in the book, we will consider min-heaps for the programmingproblem, since we will need min-heaps later in the course.
You may want to look at Problem 6-2 on page 167 of the CLRS book.
You’ll need to nd formulas for calculating the index of a node’s parent in the array, as wellas the k children of a given node.
The algorithm and the code would be much appreciated! Thanks!
Explanation / Answer
not able to paste the answer with the clear picture diagram.
below is the formula: Assume 0 as a base index array
(i-1)/k
2.child node:index i
(k*i)+1 , (k*i)+2 …. (k*i)+k
3. Non-leaf node: with the n is located at the end 1,2,3,...............n
(n-1)/k
algorithm takes lot to explain,below is the basic about the u can refer:
to find maximum:
for (int i=1; i<=k; i++)
{
if (child[i] != -1 &&
arr[child[i]] > max_child)
{
max_child_index = child[i];
max_child = arr[child[i]];
}
}
to find minimum:
for (int i=1; i<=k; i++)
{
if (child[i] != -1 &&
arr[child[i]] > min_child)
{
min_child_index = child[i];
min_child = arr[child[i]];
}
}
Complexity:O(k logkn)
Any help let me know.not able to paste the image whole description.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.