Please complete the following code. Thanks! Give an algorithm to find all nodes
ID: 3876691 • Letter: P
Question
Please complete the following code. Thanks!
Give an algorithm to find all nodes less than some value, X, in a binary heap.
Your algorithm should run in O(K), where K is the number of nodes output.
import java.util.Arrays;
public class HeapLessThan {
public static void heapify(int[] a) {
int n = a.length;
int last = getParent(n - 1);
for (int p = last; p >= 0; p--)
siftDown(a, p, n);
}
public static void siftDown(int[] a, int p, int n) {
// TODO
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static int getLeft(int p) {
// TODO
return 0;
}
public static int getRight(int p) {
return getLeft(p) + 1;
}
public static int getParent(int p) {
// TODO
return 0;
}
public static void printLessThan(int[] heap, int x) {
System.out.print("keys < " + x + ": ");
// TODO
System.out.println();
}
public static void main(String[] args) {
int[] a = new int[] { 5, 13, 2, 25, 7, 17, 20, 8, 4, };
System.out.println(Arrays.toString(a));
heapify(a);
for (int i = 0; i < a.length; i++)
printLessThan(a, a[i]);
}
}
Explanation / Answer
package demo_project;
import java.util.Arrays;
public class HeapLessThan {
public static void heapify(int[] a) {
int n = a.length;
int last = getParent(n - 1);
for (int p = last; p >= 0; p--)
siftDown(a, p, n);
}
public static void siftDown(int[] a, int p, int n) {
int l = getLeft(p);
int r = getRight(p);
int smallest = p;
if (l < n && a[l] < a[p])
smallest = l;
if (r < n && a[r] < a[smallest])
smallest = r;
if (smallest != p)
{
swap(a,p, smallest);
siftDown(a,smallest,n);
}
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static int getLeft(int p) {
return 2*p +1;
}
public static int getRight(int p) {
return getLeft(p) + 1;
}
public static int getParent(int p) {
return (p-1)/2;
}
public static void printLessThan(int[] heap, int x,int pos) {
// System.out.print("keys < " + x + ": ");
/* to check if the item exists */
if (pos >=heap.length )
return;
/* We will skip this node and all its descendants,since all of them are greater than x.*/
if (heap[pos] >= x)
{
return;
}
System.out.println(heap[pos]+" ");
printLessThan(heap,x,getLeft(pos));
printLessThan(heap,x,getRight(pos));
}
public static void main(String[] args) {
int[] a = new int[] { 5, 13, 2, 25, 7, 17, 20, 8, 4, };
System.out.println(Arrays.toString(a));
heapify(a);
for (int i = 0; i < a.length; i++)
{
System.out.println(' '+"Keys less than :" +a[i]+' ');
printLessThan(a, a[i],0);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.