配列が最小ヒープであるかどうかをチェックする方法？

Question

私は以下の配列を持っています。 n要素を含む配列が分のヒープであるかどうかを確認するにはどうすればよいですか？

Answer 1

あなたのインデックスが（インデックス0は0が含まれている - なぜ？）、1から始まるので、以下のように、あなたが与えられたノードの子のインデックスを決定することができます

• 指定されたノードのインデックスをしてみましょう'：iの2i
• インデックスの左の子年代右の子：2i + 1

の i

ランキング

したがって、ノードごとに、両方の子がノード自体よりも大きいかどうかを簡単に確認できます。

Answer 2

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 
    ); 
} 

Answer 3

おなじみの幅優先探索（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と同じです。