Building a min heap using java

Question

I tried to build a minHeap using java, this is my code:

public class MyMinHeap {

    private ArrayList<Node> heap;

    public MyMinHeap() {
        heap = new ArrayList<Node>();
    }

    public MyMinHeap(ArrayList<Node> nodeList) {
        heap = nodeList;
        buildHeap();
    }

    public void buildHeap() {
        int i = heap.size() / 2;
        while (i >= 0) {
            minHeapify(i);
            i--;
        }
    }

    public Node extractMin() {
        if (heap.size() <= 0) return null;
        Node minValue = heap.get(0);
        heap.set(0, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);
        minHeapify(0);
        return minValue;
    }

    public String toString() {
        String s = "";
        for (Node n : heap) {
            s += n + ",";
        }
        return s;
    }

    public void minHeapify(int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        int smallest = i;

        if (left < heap.size() - 1 && lessThan(left, smallest))
            smallest = left;

        if (right < heap.size() - 1 && lessThan(right, smallest))
            smallest = right;

        if (smallest != i) {
            swap(smallest, i);
            minHeapify(smallest);
        }
    }

    private void swap(int i, int j) {
        Node t = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, t);
    }

    public boolean lessThan(int i, int j) {
        return heap.get(i)
                   .compareTo(heap.get(j)) < 0;
    }

    public static void main(String[] args) {
        char[] chars = {'a', 'b', 'c', 'd', 'e', 'f'};
        int[] freqs = {45, 13, 12, 16, 9, 5};

        ArrayList<Node> data = new ArrayList<Node>();
        for (int i = 0; i < chars.length; i++) {
            data.add(new Node(chars[i], freqs[i]));
        }

        MyMinHeap heap = new MyMinHeap(data);

        System.out.println("print the heap : " + heap);
        for (int i = 0; i < chars.length; i++) {
            System.out.println("Smallest is :" + heap.extractMin());
        }

    }
}

The output should be:5,9,12,13,16,45,

but what I got is : 9,13,12,16,45

I have debugged this but still can't figure out, anybody help? thanks a lot.

Answer 1

Insert : When we insert into a min-heap, we always start by inserting the element at the bottom. We insert at the rightmost spot so as to maintain the complete tree property. Then, we "fix" the tree by swapping the new element with its parent, until we find an appropriate spot for the element. We essentially bubble up the minimum element. This takes 0 (log n) time, where n is the number of nodes in the heap.

Extract Minimum Element : Finding the minimum element of a min-heap is easy: it's always at the top. The trickier part is how to remove it. (I n fact, this isn't that tricky.) First, we remove the minimum element and swap it with the last element in the heap (the bottommost, rightmost element). Then, we bubble down this element, swapping it with one of its children until the minheap property is restored. Do we swap it with the left child or the right child? That depends on their values. There's no inherent ordering between the left and right element, but you'll need to take the smaller one in order to maintain the min-heap ordering.

public class MinHeap {

    private int[] heap;
    private int size;
    private static final int FRONT = 1;

    public MinHeap(int maxSize) {
      heap = new int[maxSize + 1];
      size = 0;
    }

    private int getParent(int position) {
      return position / 2;
    }

    private int getLeftChild(int position) {
      return position * 2;
    }

    private int getRightChild(int position) {
      return position * 2 + 1;
    }

    private void swap(int position1, int position2) {
      int temp = heap[position1];
      heap[position1] = heap[position2];
      heap[position2] = temp;
    }

    private boolean isLeaf(int position) {
      if (position > size / 2) {
        return true;
      }
      return false;
    }

    public void insert(int data) {
      heap[++size] = data;
      int currentItemIndex = size;
      while (heap[currentItemIndex] < heap[getParent(currentItemIndex)]) {
        swap(currentItemIndex, getParent(currentItemIndex));
        currentItemIndex = getParent(currentItemIndex);
      }
    }

    public int delete() {
      int item = heap[FRONT];
      swap(FRONT, size--); // heap[FRONT] = heap[size--];
      heapify(FRONT);
      return item;
    }

    private void heapify(int position) {
      if (isLeaf(position)) {
        return;
      }
      if (heap[position] > heap[getLeftChild(position)]
          || heap[position] > heap[getRightChild(position)]) {
        // if left is smaller than right
        if (heap[getLeftChild(position)] < heap[getRightChild(position)]) {
          // swap with left
          swap(heap[position], heap[getLeftChild(position)]);
          heapify(getLeftChild(position));
        } else {
          // swap with right
          swap(heap[position], heap[getRightChild(position)]);
          heapify(getRightChild(position));
        }
      }
    }

    @Override
    public String toString() {
      StringBuilder output = new StringBuilder();
      for (int i = 1; i <= size / 2; i++) {
        output.append("Parent :" + heap[i]);
        output
            .append("LeftChild : " + heap[getLeftChild(i)] + " RightChild :" + heap[getRightChild(i)])
            .append("\n");
      }
      return output.toString();
    }

    public static void main(String... arg) {
      System.out.println("The Min Heap is ");
      MinHeap minHeap = new MinHeap(15);
      minHeap.insert(5);
      minHeap.insert(3);
      minHeap.insert(17);
      minHeap.insert(10);
      minHeap.insert(84);
      minHeap.insert(19);
      minHeap.insert(6);
      minHeap.insert(22);
      minHeap.insert(9);

      System.out.println(minHeap.toString());
      System.out.println("The Min val is " + minHeap.delete());
    }
  }

Answer 2

The problem is in your minHeapify function. You have:

public void minHeapify(int i) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    int smallest = i;

    if (left < heap.size() - 1 && lessThan(left, smallest))
        smallest = left;

    if (right < heap.size() - 1 && lessThan(right, smallest))
        smallest = right;

Now, let's say that your initial array list is {3,2}, and you call minHeapify(0).

left = 2 * i + 1;  // = 1
right = 2 * i + 2; // = 2
smallest = i;      // 0

Your next statement:

if (left < heap.size() - 1 && lessThan(left, smallest))

At this point, left = 1, and heap.size() returns 2. So left isn't smaller than heap.size() - 1. So your function exits without swapping the two items.

Remove the - 1 from your conditionals, giving:

    if (left < heap.size() && lessThan(left, smallest))
        smallest = left;

    if (right < heap.size() && lessThan(right, smallest))
        smallest = right;