Jak sprawdzić, czy tablica jest stertą min?

Question

Mam następujące tablice. W jaki sposób mogę sprawdzić, czy tablica zawierająca n elementów jest stertą min ?

Answer 1

Ponieważ indeks zaczyna się od 1, (indeks 0 zawiera 0 - dlaczego?), Można określić indeks dzieci danego węzła w następujący sposób:

• Niech indeks danego węzła być i
• Indeks i 'lewego dziecka s: 2i
• Indeks i' s prawego dziecka: 2i + 1

Dzięki temu dla każdego węzła można z łatwością sprawdzić, czy oba dzieci są większe niż sam węzeł.

Answer 2

is_heap to świetna propozycja. Musisz tylko użyć odpowiedniego komparatora. A można nawet używać go z indeksowaniem 1, zgodne z iteratorów, bez wysiłku:

#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

Znajomy przeszukiwanie wszerz (BFS) mogą być również stosowane w celu sprawdzenia, czy drzewo jest minimalna/maksymalna sterty lub nie.

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

Pomysł jest podobny do tego z wookie919.