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

• greybeard: (How about doc comments?) How did/do you test this? (Doubtful about if (rightChild > count) break;)
• Bahodir Boydedayev: I haven't created doc yet. I did test it, it is working well. if (rightChild > count) -> because as sorted part is stored on the right side, I don't have to check until the end of the array length

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

• Bahodir Boydedayev: Thank you so much ! .Yes, I am implementing with basic theory that I learnt from the book first and going through with codes that others have done. You gave me great feedback and suggestions. Everything is correct that you mentioned above. I will fix it and do my best, thanks !