Implement an array-based min-heap with offer (sift up) and poll (sift down). Print the internal array after inserting the values, then poll everything to produce sorted output.
Solution
Main.java
import java.util.Arrays;
public class Main {
static class MinHeap {
private int[] a = new int[4];
private int size;
void offer(int x) {
if (size == a.length) a = Arrays.copyOf(a, size * 2);
a[size] = x;
int i = size++;
while (i > 0 && a[(i - 1) / 2] > a[i]) { // sift up while smaller than the parent
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
int poll() {
int min = a[0];
a[0] = a[--size]; // move the last element to the root
int i = 0;
while (true) { // sift down to the smaller child
int l = 2 * i + 1, r = l + 1, s = i;
if (l < size && a[l] < a[s]) s = l;
if (r < size && a[r] < a[s]) s = r;
if (s == i) break;
swap(i, s);
i = s;
}
return min;
}
boolean isEmpty() { return size == 0; }
private void swap(int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
@Override public String toString() { return Arrays.toString(Arrays.copyOf(a, size)); }
}
public static void main(String[] args) {
MinHeap h = new MinHeap();
for (int x : new int[]{9, 4, 7, 1, 8, 2, 6}) h.offer(x);
System.out.println("heap array: " + h);
StringBuilder sb = new StringBuilder();
while (!h.isEmpty()) sb.append(h.poll()).append(h.isEmpty() ? "" : " ");
System.out.println("sorted: " + sb);
}
}
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!