java - 最小堆算法

标签 java algorithm sorting heap

这是我的 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。谁能看出这个最小堆算法有什么明显的问题?

最佳答案

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

由于数组从索引 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

关于java - 最小堆算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8901093/

相关文章:

java - 有没有办法删除 Eclipse 运行配置上的元数据?

java - 如何在 Android Studio 中创建项目特定的文件模板?

java - 运行 Eclipse 时它无法启动并导致错误

algorithm - 时间序列数组查找峰谷

algorithm - 在 2^n 组合中找到最佳顺序

java - 抽象通用类

java - MinMax 算法无法正常工作

linux - 使用 shell 对行条目进行排序

java - 使用 System.out.println 输出后可以更改一行吗?

c++ - 如何在C++中按特定列的值对2D字符串数组进行排序?