here is the code....
public class BuildMinHeapProblem {
static int[] heap = {
80,
90,
32,
1,
40,
50,
45,
22,
12,
23,
33
};
static int smallest;
static int left; //left child index
static int right; //right child index
static int temp;
public static void main(String[] args) {
buildMinHeap();
for (int k: heap) {
System.out.print(k);
System.out.print(" ");
}
}
public static void buildMinHeap() {
for (int p = heap.length / 2 - 1; p >= 0; p--) {
min_Heapify(p);
}
}
public static void min_Heapify(int p) {
left = leftChild(p);
right = rightChild(p);
if ((left < heap.length) && (heap[left] < heap[p]))
smallest = left;
else smallest = p;
if ((right < heap.length) && (heap[right] < heap[smallest]))
smallest = right;
if (smallest != p) {
swap(smallest, p);
min_Heapify(smallest);
}
}
public static int leftChild(int k) {
return (2 * k + 1);
}
public static int rightChild(int i) {
return (2 * i + 2);
}
public static void swap(int a, int b) {
temp = heap[a];
heap[a] = heap[b];
heap[b] = temp;
}
}
No comments:
Post a Comment