混淆兩種不同的實現堆的

Question

功能1

void min_heapify(int arr[],int n, int i){ 
    int j, temp; 
    temp = arr[i]; 
    j = 2 * i; 

    while (j <= n) 
    { 
     if (j < n && arr[j+1] < arr[j]) 
      j = j + 1; 
     if (temp < arr[j]) 
      break; 
     else if (temp >= arr[j]) 
     { 
      arr[j/2] = arr[j]; 
      j = 2 * j; 
     } 
    } 

    arr[j/2] = temp; 
} 

功能2

void max_heapify(int arr[], int n, int i)  
{ 
    int largest = i; // Initialize largest as root 
    int l = 2*i + 1; // left = 2*i + 1 
    int r = 2*i + 2; // right = 2*i + 2 

    // If left child is larger than root 
    if (l < n && arr[l] < arr[largest]) 
     largest = l; 

    // If right child is larger than largest so far 
    if (r < n && arr[r] < arr[largest]) 
     largest = r; 

    // If largest is not root 
    if (largest != i) 
    { 
     swap(arr[i], arr[largest]); 

     // Recursively heapify the affected sub-tree 
     heapify(arr, n, largest); 
    } 
} 

問題詳細信息

這裏heapification相同的方式工作，以使min_heap但問題是，我在以下問題中使用了堆他們解決了這個問題，但不幸的是，我通過觀看MIT講座實現的功能2對這個問題沒有效果，在網絡上查找了一段時間後，我發現第一個功能可以無縫地解決這個問題。我只是困惑，他們不是一樣的功能？ ------

問題

燁!!問題名稱反映了您的任務;只需添加一組數字。但是你可能會感到自己屈尊，寫一個C/C++程序來添加一組數字。這樣的問題只會質疑你的博學。所以，讓我們添加一些獨創性的味道。

增加操作現在需要成本，成本是這兩個要添加的總和。因此，加1和10，你如果要加1，2和3。有幾種方法需要的11成本 -

1 + 2 = 3, cost = 3 
1 + 3 = 4, cost = 4 
2 + 3 = 5, cost = 5 
3 + 3 = 6, cost = 6 
2 + 4 = 6, cost = 6 
1 + 5 = 6, cost = 6 
Total = 9 
Total = 10 
Total = 11 

我希望你已經明白了你的使命，要添加整數集合，使成本最低。

輸入

每個測試用例將一個正數，N（2≤N≤5000），隨後加入N-正整數開始（所有都小於100000）。輸入由N值爲零的情況終止。這種情況下不應該被處理。

輸出

對於每種情況下打印另外的最小總成本在單行中。

SampleInput

3  
1 2 3  
4  
1 2 3 4  
0  

SampleOutput

9 
19 

Answer 1

好吧，我找到了解決辦法有在條件檢查錯誤，在if條件中，我們檢查是否（前面< = n）這是之前（留下<n），因此它不能解決這個問題。好的謝謝。

void min_heapify(int arr[],int n, int i){  
    int lowest = i; // Initialize lowest as root 
    int left = 2*i ; 
    int right = 2*i + 1; 



// If child is lower than root 
    if(left <= n && arr[left] < arr[lowest]){ 
     lowest = left; 
    } 

    // If right child is lower than lowest 
    if(right <= n && arr[right] < arr[lowest]){ 
     lowest = right; 
    } 
    // If lowest is not root 
    if(lowest != i){ // also break condition 
     swap(arr[i], arr[lowest]); 

     //Recursively heapify 
     min_heapify(arr, n, lowest); 

    } 

Answer 2

有與函數2的swap功能的問題。

C是由值呼叫，所以

swap(arr[i], arr[largest]); 

不能在陣列中交換值。

一個交換功能需要的值的地址交換：

swap(int *v1, int *v2) { 
    int tmp = *v1; 
    *v1 = *v2; 
    *v2 = tmp; 
} 

和呼叫將是：

swap(&arr[i], &arr[largest]);