Как снизить стоимость функции Maxheap Heapsorts с 2lg(n) до ~lg(n)? (Ява)

Вот программа heapsort.

public class HeapSort{

private static int[] a;
private static int n;
private static int left_child;
private static int right_child;
private static int largest;

public static void main(String[] args) {
    Scanner input = new Scanner( System.in );
    System.out.println("What size of an array would you like?");
    int y = input.nextInt();
    int[] heapvictim = new int[y];

    for (int z=0;z<heapvictim.length;z++)
    {
        System.out.println("Insert Integer at Array["+z+"]");
        heapvictim[z] = input.nextInt();
    }
    System.out.println("Unsorted Array:");

    for(int z=0;z<heapvictim.length;z++)
        System.out.print(heapvictim[z]+" ");

    System.out.println();
    System.out.println("Sorted Array:");
    sort(heapvictim);
    for(int i=0;i<heapvictim.length;i++){
        System.out.print(heapvictim[i] + " ");
    }
}

public static void sort(int []a0){
    a=a0;
    buildheap(a);        
    for(int i=n;i>0;i--){
        exchange(0, i);
        n=n-1;
        maxheapify(a, 0);
    }
}

public static void buildheap(int []a){
    n=a.length-1;
    for(int i=n/2;i>=0;i--){
        maxheapify(a,i);
    }
}

public static void maxheapify(int[] a, int i){ 
    left_child=2*i+1;
    right_child=2*i+2;
    if(left_child <= n && a[left_child] > a[i]){
        largest=left_child;
    }
    else{
        largest=i;
    }

    if(right_child <= n && a[right_child] > a[largest]){
        largest=right_child;
    }
    if(largest!=i){
        exchange(i,largest);
        maxheapify(a, largest);
    }
}

public static void exchange(int i, int j){
    int t=a[i];
    a[i]=a[j];
    a[j]=t; 
    }
}

В функции maxheapify, чтобы определить, нужно ли увеличивать до левого или правого дочернего элемента, она выполняет два сравнения. В худшем случае это будет означать, что будет выполнено два сравнения, умноженные на высоту дерева ( lg(n) ). Это означает, что maxheapify имеет стоимость 2*lg(n). Как я могу изменить maxheapify, чтобы для этого требовалось всего около 1 * lg (n)?

Мне подсказали, что я могу использовать бинарный поиск рекурсивно, но я понятия не имею, как это сделать.

Я ценю любую помощь / понимание!