Implemented heapsort algorithm in Java

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

• (How about doc comments?) How did/do you test this? (Doubtful about if (rightChild > count) break;) Dec 8, 2017 at 8:49
• 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 Dec 8, 2017 at 22:09

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.

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

• 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 ! Jan 4, 2018 at 17:58