Implemented heapsort algorithm in Java

Question

I am learning algorithms by using Java. Here is an implementation of heapsort. Let me know if anything is wrong and and suggestion to improve the algorithm.

public class HeapSort {
    public int arr[];

    public HeapSort(int[] arr) {
        this.arr = arr;
    }

    // to make a heap
    public void makeHeap() {
        for (int i = 0; i < arr.length; i++) {
            // index of child element
            int index = i;
            while (index != 0) {
                int parent = (index - 1) / 2;
                if (arr[index] <= arr[parent]) break;
                // swap child element to its parent one
                int temp = arr[index];
                arr[index] = arr[parent];
                arr[parent] = temp;
                index = parent;
            }
        }
    }

    // to remove item from the top of the binary tree -> arr[0]
    public void removeTopItem(int count) {
        int a = arr[0];
        arr[0] = arr[count];
        arr[count] = a;
        int index = 0;
        count--;
        // to remake binary tree
        while (true) {
            int leftChild = index * 2 + 1;
            int rightChild = index * 2 + 2;

            // check the boundary
            if (rightChild > count) break;
            if (arr[index] > arr[leftChild] && arr[index] > arr[rightChild]) break;

            // to get greater parent
            int parentGreat = arr[rightChild] > arr[leftChild] ? rightChild : leftChild;

            // swap current item to its parent one
            int temp = arr[index];
            arr[index] = arr[parentGreat];
            arr[parentGreat] = temp;
            index = parentGreat;
        }
    }

    // sort using by heap
    public int[] heapSort() {
        // make a heap
        makeHeap();
        // sorting
        for (int i = arr.length - 1; i >= 0; i--) {
            removeTopItem(i);
        }
        return arr;
    }
}

Answer 1

I did test it, it is working well. Well,

    System.out.println(Arrays.toString(
        new HeapSort(new int[] {3, 2, 1}).heapSort()));

isn't working.

• document/comment your code.
  You commented (all public method) members, see above for standard tool support.
  For every non-trivial piece of code, what is the reason it is there, in the first place?
  Starting at the class-, if not package-level:

  /** HeapSort as a <code>java.util.function.UnaryOperator<T></code>.
   * Java & coding beginner's exercise
   *  in type design and algorithm implementation.
   * The general idea is to turn the array into a max-heap
   *  and repeatedly move the max item
   *  from the shrinking heap to its current end. 
   */
  class HeapSort<T> implements In_placeSorter<T> {
      @Override
      public T sort(T toBeSorted) {
          if (!(toBeSorted instanceof int[]))
              throw new IllegalArgumentException("int[] only, for now");
          comparables = (int[]) toBeSorted;
          return (T) sort();
      } …
  

  (note sort() not (doc)commented here: inherits from In_placeSorter<T>)

• name things for what use they are. arr is horribly unspecific (used comparables instead).
• don't make things more visible than they need to be. When in doubt, start with default/not specifying visibility:
  int comparables[];
• pay attention to boundaries:
  neither the loop in makeHeap() nor the one in heapSort() need to handle index 0.
  More importantly, while it is true that a right child needs to exist to be handled: what about left?
• trying to implement "the general idea" without looking what&how others have done is a great step in learning —
  please precede it by considering how do I know/check the specification is met?

• asking how to improve the procedure is another great step in programming
  (professionals prefix a when and). Start with algorithm;
  Just don't try to force it - if nothing suggests itself, turn to something else temporarily, sleep on it, or now look what others have done and how, for heap-sort:

  • why do heapify()s start at the middle of the array?
  • what is to be gained from not comparing the item to be (re-)inserted while there are two children?

  Continue with coding: e.g., there are several instances where you exchange/swap elements: "factor out" a method/procedure

• handle petty concerns last, if at all:
  Java arrays & java.util.Arrays don't come with a swap()? Use java.util.Collections.swap(java.util.List, int, int) as a template
  using a for-loop:
  for (int index = i, parent ; index != 0 ; index = parent) {…

Just in case:

/** Rearranges items in ascending "natural" order. */
interface In_placeSorter<T> extends java.util.function.UnaryOperator<T> {
    /** Rearranges items in ascending "natural" order.
     * @param toBeSorted items to be sorted
     * @return <code>toBeSorted</code> */
    T sort(T toBeSorted);
    @Override
    default T apply(T t) { return sort(t); }
}