最小堆算法

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 = * 2 + 1

Answer 2

我相信，你的方式寻父和/或者孩子不正确。

想一想，如果剩下的孩子在index1和index2的权利，我怎样才能到他们的父母在index0？

如何找到index0的孩子（index1和index2）？

Answer 3

的folllwing代码是在Python，但我将突出显示做繁重的线，并且在该过程希望呈现创建最小堆

heapArray = [] 
for heapKey in someArray: 
    insert(heapArray, int(heapKey)) 
return heapArray; 

def insert(heapArray, heapKey): 
    heapArray.append(heapKey) 
    index_of_key = len(heapArray)-1 
    parent_index_of_key = (index_of_heap_key-1)/2 
    while index_of_key>0: 
    if(heapKey < heapArray[parent_index_of_key]): 
     __swap(index_of_key, parent_index_of_key, heapArray) 
     index_of_key = parent_index_of_key; 
     parent_index_of_key = (index_of_key-1)/2 
    else: 
     break # we have reached the right spot 

在上述例子中的不同的解决方案，我们重新创建堆（是的，这意味着更多的内存，但出于说明的目的，这可能是一个好的开始）。在我们创建堆时，我们只需检查新插入的键的值（通过parent_index_of_key）。

如果父项大于其子项，则我们交换该值并更新索引（对于交换的密钥及其新父项）。我们重复这个过程，直到我们已经达到堆的顶部或者堆密钥不能再继续上行为止

就地交换显然更有效率，但上述内容更加直观和简单跟随。显然，我不会使用上面的代码，其中内存是一个很大的约束，但是会考虑代码简洁性和清晰性胜过内存使用情况。