HeapSort implementation

Question

I have implemented the heap sort algorithm which passes my tests. Although, I would like to ask you if I can improve anything from readability to performance.

import java.util.List;

/**
 * Created by Orestis on 17/07/2015
 */

public class HeapSort {

    public static <T extends Comparable<? super T>> void sort(List<T> list) {
        heapSort(list);
    }


    private static <T extends Comparable<? super T>> void heapSort(List<T> list){
        int heapSize = list.size() - 1;
        buildMaxHeap(list, heapSize);
        for (int i = list.size() - 1; i >= 1; i--) {
            exchange(0, i, list);
            heapSize--;
            maxHeapify(list, 0, heapSize);
        }
    }

    /**
     *
     * Maintain the max-heap property (list[find_parent(i)] >= list[i])
     * If the max-heap property is violated float down list[i]
     */
    private static <T extends Comparable<? super T>> void maxHeapify(List<T> list, int index, int heapSize) {
        int largest = index; // initialise largest to index.

        int left = findLeftIndex(index);
        int right = findRightIndex(index);

        if (left <= heapSize && list.get(left).compareTo(list.get(index)) >= 1) {
            largest = left;
        }

        if (right <= heapSize && list.get(right).compareTo(list.get(largest)) >= 1) {
            largest = right;
        }

        if (largest != index) {
            exchange(index, largest, list);
            maxHeapify(list, largest, heapSize);
        }
    }

    /**
     *
     * This function goes through the remaining nodes of the heap tree and
     * runs maxHeapify on each one.
     */
    private static <T extends Comparable<? super T>> void buildMaxHeap(List<T> list, int heapSize) {
        int start = (int) Math.floor((heapSize / 2));
        for (int i = start; i >= 0; i--) {
            maxHeapify(list, i, heapSize);
        }
    }

    private static <T extends Comparable<? super T>> void exchange(int i, int largest, List<T> array){
        T temp = array.get(largest);
        array.set(largest, array.get(i));
        array.set(i, temp);
    }

    private static int findParentIndex(int index) {
        return (index >> 1) ^ 1;
    }

    private static int findLeftIndex(int index) {
        return (index << 1) ^ 1;
    }

    private static int findRightIndex(int index) {
        return (index << 1) + 2;
    }
}

Answer 1

What comes to performance, it will degrade drastically if you pass a LinkedList (which implements java.util.List interface accepted in your heap sort): for such a list, get(int) operation runs not in constant time, but rather \$O(n)\$. In order to deal with it, check in your sort that the input list is not a linked list, and if it is, copy all the elements to an ArrayList, sort it, and load back to the input list.

The second point concerns the sifting algorithm. If the indices of the sifting operations are \$i_1, i_2, ..., i_n\$, you first swap \$i_1\$ with \$i_2\$, then \$i_2\$ with \$i_3\$ and so on until the element is in its proper place \$i_n\$. You can do better: save the element at \$i_1\$, then move \$i_2\$ to \$i_1\$, \$i_3\$ to \$i_2\$, and so on. Finally, just set the saved element at index \$i_n\$. This optimization does not improve the time complexity of heap sort, yet it reduces the constant factors hidden by the big-O notation.

The last, but not least: sometimes we do not need to sort the entire array/list. For this, it makes sense to code up a sorting routine, which can sort particular ranges. Then, in order to sort the entire array/list - as you do - you can just do:

sort(List<T> list) {
    sort(list, 0, list.size());
}

Answer 2

• Instead of:

  heapSize--;
  maxHeapify(list, 0, heapSize);
  

  you could shorter write:

  maxHeapify(list, 0, --heapSize);
  

• Instead of:

  int start = (int) Math.floor((heapSize / 2));
  

  you could use Math.floorDiv() which is shorter and most probably more performant, as well:

  int start = Math.floorDiv(heapSize, 2);