BinaryHeapSort is binary max heap based sorting implementation where root is at
ID: 3824285 • Letter: B
Question
BinaryHeapSort is binary max heap based sorting implementation where root is at index 1. Modify the implementation, without changing the class or method signatures, to have root at index 0. Also, answer these questions:
a) If a node is at index k , what is its parent’s index?
b) If a node is at index k , what is its left child index?
c) If a node is at index k , what is its right child’s index?
d) What is the largest index of a node has at least a child in a heap with n nodes?
Given Code:
public class BinaryHeapSort {
public static <T extends Comparable<T>> void sort(T[] a) {
int n = a.length-1;
// Start building initial heap
for (int k = n/2; k >= 1; k--) {
sink(a, k, n);
}
// Start Sorting
while (n > 1) {
// swap the largest element and element at index n, decrement n
SortUtils.swap(a, 1, n--);
// restore heap (from a[1] to a[n] ) order
sink(a, 1, n);
}
}
private static <T extends Comparable<T>> void sink(T[] a, int k, int lastIndex) {
while (2 * k <= lastIndex) {
int j = 2 * k;
if (j < lastIndex && SortUtils.isLessThan(a[j], a[j + 1]))
j++;
if (!SortUtils.isLessThan(a[k], a[j]))
break;
SortUtils.swap(a, k, j);
k = j;
}
}
}
Explanation / Answer
For Binary tree,When a root starts with index 0.
(a) If a node is at index k then parent's index = (k-1)/2
(b) If a node is at index k ,then left child index = (2*k+1)
(c)If a node is at index k , then right child’s index = (2*k+2)
(d) largest index of a node has at least a child in a heap with n nodes = (n-1)/2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.