0

这是到目前为止的堆排序程序。

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)？

我得到一个提示说我可以递归地使用二进制搜索，但我一点也不知道如何这样做。

我感谢任何帮助/见解！

4

1 回答 1

0

我不这么认为。在 heapify 中，您必须找到 3 个节点的最小值/最大值 - 父节点、左子节点和右子节点。如何在一次比较中找到最小值 3？

无论如何，如果您删除递归并将其放入循环中，您将获得更好的性能 - 假设它还没有进行尾部优化。

如果你仍然好奇，看看这个和这个快速实现。

于 2013-09-10T18:48:15.843 回答