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");
 //...
}