Finding a more efficient heap sort?

The most straight-forward way to perform heapsort is to use a separate heap and add all the elements to it, then the elements will be in order when we pop them out one by one. This is what "adding the elements one at a time" refers to in the statement, and this is what your implementation is doing: create a heap of type ArrayHeap and insert the elements of data to it, in the end pop the elements back to data.

A more efficient way (in terms of both space and time) is to perform in-place sorting, where we use the array to be sorted as the heap, rather than using additional memory for the heap, this is what "order the entire list at once" refers to. The steps of this implementation is as follow, we will order the elements in non-decreasing order:

1. We max-heapify the input array (i.e. we re-arrange the elements in the array so that it follows the max-heap property.
2. For i = n - 1 to 1:
   1. Swap the 0-th element in the array with the i-th element.
   2. Decrease the size of the heap by 1 (i.e. the heap should be of size i).
   3. Perform the sift-down operation on the heap to restore the max-heap property.

Note that whenever the max-heap property holds, the top-most element in the heap is the largest element, so at the start of the k-th iteration (k = n - i here) the 0-th element is the k-largest element, and we place is in the correct position in the array by swapping.

Note that step 1 can be done in O(n), and in step 2 there are O(n) iterations and each sift-down operation takes time O(log(n)), so the overall time complexity is O(n log(n)).

Below is an implementation in Java for your reference:

import java.util.Random;

public class HeapSort {
    public static void main(String[] args) {
        for (int i = 1; i <= 10; i++) {
            System.out.println(String.format("Iteration number %d%n", i));
            Integer[] array = randomIntArray(10, 0, 100);
            System.out.println(String.format("Array before sorting: [%s]", toStr(array)));
            heapSort(array);
            System.out.println(String.format("Array after sorting: [%s]", toStr(array)));
            System.out.println("================================================================");
        }
    }

    private static <T extends Comparable<T>> T[] heapSort(T[] array) {
        maxHeapify(array, array.length);

        for (int i = array.length - 1; i > 0; i--) {
            swap(array, 0, i);
            siftDown(array, i, 0);
        }

        return array;
    }

    private static <T extends Comparable<T>> void maxHeapify(T[] array, int heapSize) {
        for (int i = getParentIdx(heapSize - 1); i >= 0; i--) {
            siftDown(array, heapSize, i);
        }
    }

    private static <T extends Comparable<T>> void siftDown(T[] array, int heapSize, int idx) {
        final int length = Math.min(array.length, heapSize) - 1;
        if (idx > length || idx < 0) throw new IllegalArgumentException("Index out of range");

        while (true) {
            int maxIdx = idx;
            int leftChildIdx = getLeftChildIdx(idx);
            int rightChildIdx = getRightChildIdx(idx);

            if (leftChildIdx <= length && array[maxIdx].compareTo(array[leftChildIdx]) < 0) maxIdx = leftChildIdx;
            if (rightChildIdx <= length && array[maxIdx].compareTo(array[rightChildIdx]) < 0) maxIdx = rightChildIdx;

            if (idx != maxIdx) {
                swap(array, idx, maxIdx);
                idx = maxIdx;
            } else {
                return;
            }
        }
    }

    private static int getParentIdx(int idx) {
        return (idx - 1) / 2;
    }

    private static int getLeftChildIdx(int idx) {
        return idx * 2 + 1;
    }

    private static int getRightChildIdx(int idx) {
        return idx * 2 + 2;
    }

    private static <T> void swap(T[] array, int i, int j) {
        T tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private static <T> String toStr(T[] array) {
        StringBuilder sb = new StringBuilder();
        for (T element : array) {
            sb.append(element + ", ");
        }

        return sb.substring(0, sb.length() - 2);
    }

    private static Integer[] randomIntArray(int size, int lowerBound, int upperBound) {
        Integer[] result = new Integer[size];
        Random random = new Random();
        int diff = upperBound - lowerBound + 1;
        for (int i = 0; i < size; i++) result[i] = lowerBound + random.nextInt(diff);
        return result;
    }
}