java - Heapsorts の Maxheap 関数のコストを 2lg(n) から ~lg(n) に下げるにはどうすればよいですか? (ジャワ)

Question

これまでのヒープソートプログラムは次のとおりです。

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 関数では、左または右の子にヒープ化するかどうかを決定するために、2 つの比較が行われます。最悪の場合、これはツリーの高さ ( lg(n) ) の 2 倍の比較を行うことを意味します。これは、maxheapify のコストが 2*lg(n) であることを意味します。maxheapify を変更して、約 1*lg(n) しか必要としないようにするにはどうすればよいですか?

バイナリサーチを再帰的に使用できるというヒントを得ましたが、その方法についてはまったく手がかりがありません。

ヘルプ/洞察に感謝します！