कैसे जांचें कि सरणी एक न्यूनतम ढेर है या नहीं?

Question

मेरे पास निम्न सरणी है। मैं कैसे जांच सकता हूं कि एन तत्व युक्त सरणी न्यूनतम ढेर है या नहीं?

Answer 1

के बाद से अपने सूचकांक 1 से शुरू होता है, (सूचकांक 0 होता है 0 - क्यों?), किसी विशेष नोड के बच्चों के सूचकांक इस प्रकार का निर्धारण कर सकते हैं: दिए गए नोड के सूचकांक

• चलो हो i
• i के सूचकांक के बाईं बच्चे: 2i
• i सूचकांक ': 2i + 1

सही बच्चे

इस प्रकार प्रत्येक नोड के लिए, आप आसानी से जांच सकते हैं कि दोनों बच्चे नोड से अधिक हैं।

Answer 2

is_heap एक अच्छा सुझाव है। आपको बस उचित तुलनित्र का उपयोग करने की आवश्यकता है। चाहे पेड़ एक न्यूनतम/अधिकतम ढेर है या नहीं की जाँच करने के

#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) भी लागू किया जा सकता: और तुम भी यह iterators के साथ अपने 1-आधारित अनुक्रमण के साथ, आसानी से उपयोग कर सकते हैं।

#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 जैसा ही है।