java - 最小堆算法

Question

这是我的 minHeap 算法，但它没有按预期运行:

public static int [] fixheap(int heap[], int n, int i){
    int j=2*i;
    int weight = heap[i];

    while (j<=n){
        if((j<n) && heap[j] > heap[j+1])
            j++;
        if(weight <= heap[j]) break;
        else 
        heap[j/2] = heap[j]; 

        j=j*2;
    }

    heap[j/2]= weight;

    return heap;
}

public static void makeheap(int heap[], int n){

    for (int i=n/2; i>=0; i--){
        fixheap(heap, n ,i);
    }   
}

当数据元素以各种顺序添加时，算法返回不正确的 minHeaps。谁能看出这个最小堆算法有什么明显的问题？

Answer 1

您正在比较用于形成堆的数组的错误元素。尝试试运行你的程序

由于数组从索引 0 开始，所以这里最初应该取 i=n/2-1。

public static void makeheap(int heap[], int n){

     for (int i=n/2 - 1; i>=0; i--){
     fixheap(heap, n ,i);
    }   
}

然后您将不得不更改您的 fixheap 函数以获得 j 的正确值

j = i*2 + 1