Heapsort algorithm details:

Worst-case Time Complexity: O(n log(n))

Space Complexity: O(1)

 

The algorithm

The heapsort algorithm is an in-place, comparison based sorting algorithm. In the core of the algorithm (as the name suggest), the use of the heap data structure is improving the time complexity. In a nutshell, heap is a special type of tree, where the elements in the tree are in a certain order to each other. This allows to find the minimum or maximum of binary heap in O(1) and insertion/deletion in O(log(n)).

Heapsort is done in two parts, as first step a sub section of the collection is selected. The elements are reordered to be in max heap format, which is O(n) (where n is the selected chunk). From here the algorithm is comparing the “heapified” part of the collection, with the not ordered part recursively until no elements are left to compare. In this process the compared elements are swapped if necessary.

The performance of the heapsort algorithm is O(n log(n)) which is very impressive. I would suggest to use a default library, in a real world application as most of the languages nowadays are implementing a better performing algorithm as default sorting option. In Java the Util package contains a sort method, in the Arrays class. Based on the documentation the implementation is Dual-Pivot Quicksort which performs O(n log(n)) time complexity.

 

Java implementation

My implementation of the heapsort algorithm in java:

     <span class="pl-k">private</span> <span class="pl-k">static</span> <span class="pl-k">int</span> arrayLength;
     /**
     * Bubble sort Comparable array elements with order
     *
     * Time complexity: O(n^2)
     *
     * @param items - the objects to sort
     * @param isAsc - if true the order will be increasing (ascending)
     */
    public static void sort(Comparable[] items, boolean isAsc) {
        arrayLength = items.length - 1;
        for (int i = arrayLength / 2; i >= 0; i--) {
            heapify(items, i, isAsc);
        }

        for (int i = arrayLength; i > 0; i--) {
            swapItems(items, 0, i);
            arrayLength--;
            heapify(items, 0, isAsc);
        }
    }

    /**
     * Shift objects until heap property is fulfilled
     *
     * @param items - the objects to heapify
     * @param rootIndex - start recursion from
     * @param isAsc - order of the items
     */
    private static void heapify(Comparable[] items, int rootIndex, boolean isAsc) {
        int leftIndex = rootIndex * 2;
        int rigthIndex = leftIndex + 1;
        int greaterIndex = rootIndex;

        if (leftIndex <= arrayLength && (isAsc && items[leftIndex].compareTo(items[greaterIndex]) > 0
                || !isAsc && items[leftIndex].compareTo(items[greaterIndex]) < 0)) {
            greaterIndex = leftIndex;
        }

        if (rigthIndex <= arrayLength && (isAsc && items[rigthIndex].compareTo(items[greaterIndex]) > 0
                || !isAsc && items[rigthIndex].compareTo(items[greaterIndex]) < 0)) {
            greaterIndex = rigthIndex;
        }

        if (greaterIndex != rootIndex) {
            swapItems(items, rootIndex, greaterIndex);
            heapify(items, greaterIndex, isAsc);
        }
    }

    /**
     * Swap items in array
     *
     * @param items - the array to work with
     * @param indexOne - the first item index to swap
     * @param indexTwo - second index to swap with first
     */
    protected static void swapItems(Comparable[] items, int indexOne, int indexTwo) {
        Comparable tmp = items[indexOne];
        items[indexOne] = items[indexTwo];
        items[indexTwo] = tmp;
    }

The above code snippet is using the Comparable interface, to simplify the code. It allows to define the sorting order as ascending or descending.

The complete implementation with unit tests is available in my Java Algorithms Github Repo, https://github.com/pete314/algorithms-java

 

 

 

Share This