LearnFrenzy
Sign in Take a free test

Data Structures in Java · Data Structures in Java Programs · Question 4

Binary min-heap from scratch with heap sort in Java Solution, output & explanation

  • Program
  • Hard
  • 0 comments
  • Answer explained
  • Moderated community
Question 4 Back to Exercise

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);
    }
}

Output Verified by compiling and running

heap array: [1, 4, 2, 9, 8, 7, 6]
sorted: 1 2 4 6 7 8 9

The array is a valid heap (every parent ≤ its children) but not sorted. n polls of O(log n) each give an O(n log n) heap sort.

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!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links