java - 将最大堆排序更改为最小堆排序

Question

我正在努力研究如何将 maxHeap 更改为 minHeap。我目前有一个 maxHeap 算法在工作，但我想知道如何更改它。这是我使用的 maxHeap:

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

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

        j=j*2;
    }

    heap[j/2][0]= data;

    return heap;
}

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

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

我已经尝试反转某些看起来相关的标志，但是，我还没有找到 minHeap。任何帮助都会很棒，谢谢。

Answer 1

最小堆和最大堆之间的唯一区别是比较器。如果你有一个正常工作的最大堆结构，你应该只需要翻转比较器。

查看 Introduction to Algorithms在亚马逊上。最大堆结构的描述非常详细，可在预览或“查看内部”功能中找到。