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