Как проверить, является ли массив мини-кучей?

Question

У меня есть следующий массив. Как я могу проверить, содержит ли массив, содержащий n элементов, 0 минутную кучу ?

Answer 1

Поскольку ваш индекс начинается с 1, (индекс 0 содержит 0 - почему?), Вы можете определить индекс детей данного узла, как показано ниже:

• Пусть индекс данного узла быть i
• Индекс i 'левого ребенка s: 2i
• Индекс i' правого ребенка s: 2i + 1

Таким образом, для каждого узла вы можете легко проверить, что оба ребенка больше самого узла.

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.