如何檢查數組是否是最小堆？

我有以下數組。如何檢查包含n個元素的數組是否爲分鐘堆？ 如何檢查數組是否是最小堆？

來源

2016-07-28 user3015986

http://stackoverflow.com/questions/4157159/algorithm-for-checking-if-an-array-with-n-elements-is-a-minimum-heap請參閱此。 –

您是否在尋找['std :: is_heap']（http://en.cppreference.com/w/cpp/algorithm/is_heap）？ –

節點i的孩子在2i和2i + 1。因此，驗證一個[2i]> = a [i]和一個[2i + 1]> = a [i]，因爲這是堆性質：孩子至少和父母一樣大。 – Gene

因爲你的指數從1開始，（索引0包含0 - 爲什麼？），你能確定給定節點的子項的指標如下：

讓給定節點的索引是i
i指數的左子：2i
i指數「：2i + 1

沒錯兒

因此，對於每個節點，您可以輕鬆地檢查兩個子節點是否都大於節點本身。

來源

2016-07-28 04:01:12 wookie919

有些人喜歡將索引放在索引1處。他們說這是出於性能方面的原因（在計算左側子時消除了額外的增加，並且在計算父項時刪除了減去），但是我已經完成了性能比較：沒有意義區別。缺點是在類似C語言的程序員中會導致無數的fencepost錯誤。我認爲人們這樣做的主要原因是因爲Sedgewick在1983年寫了一本算法書，他的所有例子都在Pascal中，有1個數組。即使在今天，他的帕斯卡例子的C翻譯也很流行。 –

is_heap是一個很好的建議。你只需要使用適當的比較器。你甚至可以與你的基於1的索引迭代器使用它，毫不費力：

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <functional> 

int main() 
{ 
    std::vector<int> v {0, 5, 9, 11, 14, 18, 19 }; 
    std::cout << std::is_heap(
     v.begin()+1, // off by 1 
     v.end(), 
     std::greater<int>() // std::less is used by default for max-heap 
    ); 
}

來源

2016-07-28 04:43:26 luk32

熟悉的廣度優先搜索（BFS）也可以適用於檢查樹是否是最小/最大堆與否。

#include <iostream> 
#include <queue> 

int main() { 
    int tree[] = {5, 9, 11, 14, 18, 19, 21, 33, 17, 27}; 
    int size = 10; 
    std::queue <int> q; 
    q.push(0); 
    bool flag = true; 
    while(!q.empty()) { 
     int x = q.front(); 
     q.pop(); 
     int left = 2*x+1, right = 2*x+2; // 0-based indexing used here 
     if(left < size) { // check if left child exists or not. 
      q.push(left); 
      // check value at parent is less than child or not. 
      if(tree[x] > tree[left]) { 
       flag = false; 
       break; 
      } 
     } 
     if(right < size) { // check whether right child exists or not. 
      q.push(right); 
      if(tree[x] > tree[right]) { // check value of parent less than child. 
       flag = false; 
       break; 
      } 
     } 
    } 
    if(flag) 
     std::cout << "It is minimum heap.\n"; 
    else 
     std::cout << "Not a minimum heap.\n"; 
    return 0; 
}

這個想法與wookie919類似。

來源

2016-07-28 19:22:42 Shubham

如何檢查數組是否是最小堆？

回答

相關問題