Max heap implementation

Question

I have implemented a max-Heap data structure backed by an array. I wanted to know whether this is an acceptable implementation or not.

Any improvements or suggestions are welcome.

import java.util.Arrays;
import java.util.NoSuchElementException;

public class MaxHeapDemo {

  int heap[],heapSize=0;

public MaxHeapDemo() {
    // TODO Auto-generated constructor stub
    heapSize=0;
}

/**
 * Function to build the max-heap
 * @param inputData
 */
private  void maxHeapify(int[] inputData) {

    heap= new int [inputData.length+1];
    //fill the heap from 1 index to make life easier

    //if a parent node is at ith index the the left child is at 2*i and right child is at
    //2*i+1
    //  System.out.println("data ="+Arrays.toString(data));
    //insert from the back to the front

    for (int i = 0; i < inputData.length; i++) {
        heap[heapSize+1]=inputData[i];  

        heapify(inputData[i]);
        ++heapSize;
    }
}

/**
 * This method will balance the heap according to the properties of the heap
 * @param value
 * @param data
 */
private  void heapify( int value/*, int[] data*/) {

    //int index = data.length-1;
    int index = heapSize+1;
    //System.out.println("index "+index+" heap[index/2]"+heap[index/2]);
    while (index > 1 && heap[index/2] < value ){
        //swap parent with child
        int temp= heap[index/2];
        heap[index/2]= heap[index];
        heap[index]=temp;

        index/=2;
    }

}

/**
 * THis method remove the maximum element from the heap and re-balances the heap according
 * to the Max heap property
 * @return
 */
public  int removeMax() {


if(heapSize == 0)
    throw new NoSuchElementException("The heap is empty");

    int result=-1;

    result = heap[1];
    heap[1]=heap[heapSize];
    --heapSize;

    //now balance the heap according to the max heap property

    for (int i=1;i < heapSize ; i*=2){
        if (i*2 < heapSize && heap[i]< heap[i*2] && heap [i*2] > heap[i*2+1]){
            //swap the two elements
            int max= heap[i*2];
            heap[i*2]=heap[i];
            heap[i]= max;
        }else if (i*2+1 < heapSize && heap[i]< heap[i*2+1]){
            int max= heap[i*2+1];
            heap[i*2+1]=heap[i];
            heap[i]= max;
        }
    }
    System.out.println(Arrays.toString(heap));
    return result;
}
public void add(int value){
    int index = heapSize+1;
    if(index >= heap.length) heap = Arrays.copyOf(heap, heapSize + 16);
    heap[index] = value;

    while (index > 1 && heap[index/2] < heap[index]){
        //swap parent with child
        int temp= heap[index/2];
        heap[index/2]= heap[index];
        heap[index]=temp;

        index/=2;
}
}

/**
 * Main method to test the program
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub

    MaxHeapDemo heapDemo = new MaxHeapDemo();
    heapDemo.maxHeapify(new int []{3,2,6,7,9});
    System.out.println(Arrays.toString(heapDemo.heap));
    System.out.println("the maximum element is ="+heapDemo.heap[1]);
    System.out.println("remmoved max ele is = "+heapDemo.removeMax());
}
}

Answer 1

in the constructor it's better to allocate an empty array to avoid an unexpected null pointer.

In maxHeapify you should just at least initialize heapSize to 0 before the loop.

You have no other way to add a element to the heap. This would be something like this:

public void add(int value){
    int index = heapSize+1;
    if(index >= heap.length) heap = Arrays.copyOf(heap, heapSize + 16);
    heap[index] = value;

    while (index > 1 && heap[index/2] < heap[index]){
        //swap parent with child
        int temp= heap[index/2];
        heap[index/2]= heap[index];
        heap[index]=temp;

        index/=2;
    }
}

heapify depends on value being the same as the value at heap[heapSize+1] instead you can use the add above.

removeMax should throw a better exception than either returning -1 or throwing NullPointerException if the heap is empty (from being emptied or never being filled).

public  int removeMax() {
    if(heapSize == 0)
        throw new NoSuchElementException("The heap is empty");

    //...
}