Skip to main content
Typo and tags.
Source Link
rolfl
  • 98.2k
  • 17
  • 220
  • 419

I am trying to create max-heap for practivepractice.

I am trying to create max-heap for practive.

I am trying to create max-heap for practice.

added 76 characters in body
Source Link
Xin
  • 139
  • 1
  • 7

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

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

Source Link
Xin
  • 139
  • 1
  • 7

Max-heap implementation with List

I am trying to create max-heap for practive.

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();
  }
}