Max-heap implementation with List

Question

I am trying to create max-heap for practice.

Are there any bugs? Are there ways that I can improve the code quality?

public class MaxHeap <E extends Comparable<? super E>>{
 List<E> list;
 public MaxHeap(E[] array){
 this(Arrays.asList(array));
 }
 public MaxHeap(List<E> list){
 if(list == null)
 throw new IllegalArgumentException("list cannot be null");
 this.list = new ArrayList<E>(list);
 buildHeap();
 }
 public void buildHeap(){
 for(int i=lastParent(); i >= 0; i--)
 maxHeapify(i);
 }
 private void maxHeapify(int parent){
 if(isParent(parent)){
 //assume left child is bigger for now
 int biggerChild = 2 * parent + 1;
 int rightChild = biggerChild+1;
 if(rightChild < size() && compare(rightChild, biggerChild) > 0)
 biggerChild = rightChild;
 if(compare(biggerChild, parent) > 0){
 swap(biggerChild, parent);
 maxHeapify(biggerChild);
 }
 }
 }
 private int compare(int fir, int sec){
 return list.get(fir).compareTo(list.get(sec));
 }
 public boolean add(E item){
 if(item == null)
 return false;
 list.add(item);
 int child = last();
 int parent = getParent(child);
 while(isParent(parent)){
 if(compare(parent, child) < 0){
 swap(parent, child);
 child = parent;
 parent = getParent(parent);
 }
 else
 break;
 }
 return true;
 }
 private void swap(int left, int right){
 Collections.swap(list, left, right);
 }
 public int size(){
 return list.size();
 }
 public E remove(){
 if(isEmpty())
 return null;
 swap(0, last());
 E max = list.remove(last());
 maxHeapify(0);
 return max;
 }
 public boolean isEmpty(){
 return size() == 0;
 }
 private int last(){
 return size() - 1;
 }
 private int getParent(int child){
 if(index == 0)
 return -1;
 else
 return (child-1)/2;
 }
 private boolean isParent(int index){
 return index >= 0 && index <= lastParent();
 }
 private int lastParent(){
 return size()/2 - 1;
 }
 public String toString(){
 StringBuilder builder = new StringBuilder();
 int lineCounter = 0;
 int lineMax = 1;
 for(E item : list){
 builder.append(item);
 builder.append(" ");
 lineCounter++;
 if(lineCounter >= lineMax){
 builder.append("\n");
 lineCounter = 0;
 lineMax++;
 }
 }
 return builder.toString();
 }
}

• Jamal: Does it work as intended?
• Xin: @Jamal It works as far as I can tell.
• Legato: Welcome to CodeReview, Xin. While I understand wanting to check for unforeseen bugs, please keep in mind that bug fixes/error handling would qualify your question as off-topic.

Answer 1

Just a few smaller issues:

• Why expose buildHeap() when every other public method, including the constructors, already leaves you with a perfectly sorted heap?
• Why does the add() method contain sorting logic? This would usually be placed in an increment() method.
• An increment() method is missing.
• Your add() method did not copy the element. Your heap is therefore vulnerable to side effects where any of the elements you have a reference on, did get modified in the outside world. Either warn, watch, encapsulate or make immutable.
• Comments? At least your constructors and public methods should be documented, denoting which side effects are to be expected.
• There is no interface to get the sorted list back.
• The toString() method returns the internal order of the heap. Nice for debugging, but not what you would expect. You would expect it to return elements in lexicographical order.
• Please don't use it in production. Your basic MaxHeap has significantly worse runtime characteristics than the default Fibonacci Heap.
• There is a getParent() helper, but you have omitted such helpers for getLeft() and getRight(), even though you are using the corresponding expressions multiple times.