Làm thế nào để kiểm tra xem mảng là một đống tối thiểu?

Question

Tôi có mảng sau. Làm thế nào tôi có thể kiểm tra xem mảng có chứa các phần tử n là một heap tối thiểu ?

Answer 1

Kể từ khi chỉ số của bạn bắt đầu từ 1, (chỉ số 0 chứa 0 - tại sao?), Bạn có thể xác định các chỉ số của con cái một nút cho trước như sau:

• Hãy để cho chỉ số của các nút cho trước được i
• Index của i 'con trái s: 2i
• Index của i' con phải s: 2i + 1

Vì vậy, đối với mỗi nút, bạn có thể dễ dàng kiểm tra xem cả hai trẻ em có lớn hơn chính nút đó hay không.

Answer 2

is_heap là một đề xuất tuyệt vời. Bạn chỉ cần sử dụng so sánh thích hợp. Và thậm chí bạn có thể sử dụng nó với chỉ mục 1-based của bạn với vòng lặp, dễ dàng:

#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

Các quen Chiều rộng tìm kiếm đầu tiên (BFS) cũng có thể được áp dụng để kiểm tra xem cây là một tối thiểu/đống tối đa hay không.

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

Ý tưởng tương tự như ý tưởng của wookie919.