1
\$\begingroup\$

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();
  }
}
\$\endgroup\$
  • \$\begingroup\$ Does it work as intended? \$\endgroup\$ – Jamal Apr 14 '15 at 6:02
  • \$\begingroup\$ @Jamal It works as far as I can tell. \$\endgroup\$ – Xin Apr 14 '15 at 6:43
  • \$\begingroup\$ 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. \$\endgroup\$ – Legato Apr 14 '15 at 7:18
1
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.