heapsort ввод с наибольшим и наименьшим количеством сравнений

Привет, я немного огляделся и не смог найти прямого обсуждения этого вопроса. Большинство из них, похоже, охватывают временную сложность и большую нотацию O.

Мне интересно, повлияет ли и как порядок ввода в алгоритм heapsort на количество сравнений, необходимых для сортировки ввода. Например, возьмем алгоритм пирамидальной сортировки, который сортирует в порядке возрастания (от меньшего к большему).... если я ввожу набор целых чисел, уже упорядоченных таким образом (по возрастанию), сколько сравнений потребуется по сравнению с набором входных данных, который в порядке убывания (от большего к меньшему)? Как насчет сравнения с полностью рандомизированным набором тех же чисел?

public class Heap {
    // This class should not be instantiated.
    private Heap() {
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * 
     * @param pq
     *            the array to be sorted
     */
    public static void sort(Comparable[] pq) {
        int N = pq.length;
        for (int k = N / 2; k >= 1; k--)
            sink(pq, k, N);
        while (N > 1) {
            exch(pq, 1, N--);
            sink(pq, 1, N);
        }
    }

    private static void sink(Comparable[] pq, int k, int N) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(pq, j, j + 1))
                j++;
            if (!less(pq, k, j))
                break;
            exch(pq, k, j);
            k = j;
        }
    }

    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i - 1].compareTo(pq[j - 1]) < 0;
    }

    private static void exch(Object[] pq, int i, int j) {
        Object swap = pq[i - 1];
        pq[i - 1] = pq[j - 1];
        pq[j - 1] = swap;
    }

    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }
}