MinHeap implementation in Java

Question

I have made my own MinHeap in Java. I would like to get review comments on the same.

package heap.minheap;

public class MinHeap {

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

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

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

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

private int getRightChild(int position){
    return 2*position+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 currentItem = size;
    while( heap[getParent(currentItem)] > heap[currentItem] ){
        swap(getParent(currentItem),currentItem);
        currentItem = getParent(currentItem);
    }
}

public int delete(){
    int itemPopped = heap[FRONT];
    heap[FRONT] = heap[size--];
    heapify(FRONT);
    return itemPopped;
}

private void heapify(int position){
    if(isLeaf(position)){
        return;
    }

    if ( heap[position] > heap[getLeftChild(position)] || heap[position] > heap[getRightChild(position)]){

        if(heap[getLeftChild(position)] < heap[getRightChild(position)]){
            swap(position , getLeftChild(position));
            heapify(getLeftChild(position));
        }
        else{
            swap(position , 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();
}
}

Answer 1

Creating a package just for one class seems like overkill. package heap; would have been enough, I think.

---

You should offer a .getSize() method, especially since this implementation has fixed capacity, which places the responsibility of avoiding overflow on the user.

---

Index 0 of the array is wasted. I'm not worried so much about the 4 wasted bytes, but that it's an unnatural thing to do in a language with zero-based arrays. This feels more natural:

public MinHeap(int capacity) {
    this.heap = new int[capacity];
    this.size = 0;
}

To make that work…

// Note use of static keyword
private static int getLeftChild(int position) {
    return 2 * position + 1;
}

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

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

private boolean isLeaf(int position) {
    // Reuse getLeftChild() for consistency and ease of understanding
    return getLeftChild(position) >= this.size;
}

public String toString() {
    …
    // Reuse isLeaf() for consistency and ease of understanding
    for (int i = 0; !isLeaf(i); i++) {
        …
    }
    …
}

---

The output from .toString() is awkward, as many nodes can get printed more than once. (Consider building a tree-like representation.) For a tree like

     1
   /   \
  2     3
 / \   /
4   5 6

The output would be

Parent :1LeftChild : 2 RightChild :3
Parent :2LeftChild : 4 RightChild :5
Parent :3LeftChild : 6 RightChild :ArrayIndexOutOfBoundsException!!!

To avoid ambiguity, it would be better to say "Node: … LeftChild: … RightChild: …".

Answer 2

Style

• Dead code should be removed. maxSize is never used.

• Be consistent in your style. You should decide wether you use this. If a decision is made you should stick to it.

  Here i would suggest refactor the constructor to

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

Simplification

In the isLeaf() method you basically say if the condition is true, return true otherwise return false

private boolean isLeaf(int position){

    if(position > size/2){
        return true;
    }
    return false;
}

This can be simplified to return if the condition is true.

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

Answer 3

A few thoughts:

1. Heapify ensures only a section of the array follows the heap property.

   Consider array {9,8,7,6,5,4,3}. On calling heapify(1), it will result in {8,6,7,9,5,4,3}.

   Heapify API name has the assurance that the whole array is converted to a heap by one call.

2. Some optimisation can be done by storing getRightChild/getLeftChild in temp variables to avoid multiple processing for same data.

3. getLeftChild/getRightChild may return index > maxSize i.e it does not check for array bounds (toString API), say, for array {1,2,3,4}.

4. Since the implementation forces the usage of array to start from 1 unlike the usual convention, do add a comment or avoid that.

Answer 4

My thought is that heapify would be better off as a nonrecursive function, since you could easily just change it to a simple while loop:

private void heapify(int position){
    while (!isLeaf(position)){
        int left  = getLeftChild(position);
        int right = getRightChild(position);
        if (heap[position] > heap[left] || heap[position] > heap[right]){
            if (heap[left] < heap[right]){
                swap(position, left);
                position = left;
            } else {
                swap(position, right);
                position = right;
            }
        } else
            break;
    }
}

Minor things I noticed that no one has mentioned yet:

1. toString doesn't output anything for a size 1 heap.

2. Your spacing is at times inconsistent. For example, here around the comma:

   swap(getParent(currentItem),currentItem); swap(position , getLeftChild(position));

   There were also a few ifs and whiles with different spacing. It's easier to read your code if your spacing is more consistent.

All in all it was fairly clean and easy to read and understand.