C++-এ দেওয়া বাইনারি ট্রি হিপ (Heap) কিনা তা যাচাই করুন

কনসেপ্ট

দেওয়া বাইনারি ট্রি হিপ প্রপার্টি মেনে চলে কিনা তা যাচাই করুন। হিপ হওয়ার দুটি শর্ত:

• বাইনারি ট্রি সম্পূর্ণ (Complete) হতে হবে (অবশেষে লেভেল বাদে সব লেভেল ফুল)।
• প্রতিটি নোডের মান তার চাইল্ড নোডের চেয়ে বড় বা সমান হতে হবে (max-heap)।

উদাহরণ

নিচের ট্রিতে হিপ প্রপার্টি আছে:

নিচের ট্রিতে হিপ প্রপার্টি নেই:

পদ্ধতি

উপরোক্ত দুটি শর্ত আলাদা আলাদা যাচাই করুন। isComplete() ফাংশন দিয়ে কমপ্লিটনেস চেক করুন এবং isHeapUtil() দিয়ে হিপ প্রপার্টি।

isHeapUtil-এ নিচের কথাগুলো বিবেচনা করুন:

• প্রতিটি নোডের ২টি চাইল্ড, ০ চাইল্ড (লাস্ট লেভেল) বা ১ চাইল্ড (সর্বোচ্চ একটা) হতে পারে।
• নোডের চাইল্ড না থাকলে লিফ নোড, true রিটার্ন করুন (বেস কেস)।
• একটি চাইল্ড থাকলে (বাম চাইল্ড হতে হবে কারণ কমপ্লিট ট্রি) শুধু সেটির সাথে তুলনা করুন।
• দুই চাইল্ড থাকলে উভয়ের সাথে হিপ প্রপার্টি চেক করে রিকার্সন করুন।

উদাহরণ

#include <bits/stdc++.h> 
using namespace std; 

struct Node1{ 
    int key; 
    struct Node1 *left; 
    struct Node1 *right; 
}; 

struct Node1 *newNode(int k){ 
    struct Node1 *node1 = new Node1; 
    node1->key = k; 
    node1->right = node1->left = NULL; 
    return node1; 
} 

unsigned int countNodes(struct Node1* root1){ 
    if (root1 == NULL) 
        return (0); 
    return (1 + countNodes(root1->left) + countNodes(root1->right)); 
} 

bool isCompleteUtil (struct Node1* root1, unsigned int index1, unsigned int number_nodes){ 
    if (root1 == NULL) 
        return (true); 
    if (index1 >= number_nodes) 
        return (false); 
    return (isCompleteUtil(root1->left, 2*index1 + 1, number_nodes) && isCompleteUtil(root1->right, 2*index1 + 2, number_nodes)); 
} 

bool isHeapUtil(struct Node1* root1){ 
    if (root1->left == NULL && root1->right == NULL) 
        return (true); 
    if (root1->right == NULL){ 
        return (root1->key >= root1->left->key); 
    } 
    else{ 
        if (root1->key >= root1->left->key && root1->key >= root1->right->key) 
            return ((isHeapUtil(root1->left)) && (isHeapUtil(root1->right))); 
        else 
            return (false); 
    } 
} 

bool isHeap(struct Node1* root1){ 
    unsigned int node_count = countNodes(root1); 
    unsigned int index1 = 0; 
    if (isCompleteUtil(root1, index1, node_count) && isHeapUtil(root1)) 
        return true; 
    return false; 
} 

int main(){ 
    struct Node1* root1 = NULL; 
    root1 = newNode(10); 
    root1->left = newNode(9); 
    root1->right = newNode(8); 
    root1->left->left = newNode(7); 
    root1->left->right = newNode(6); 
    root1->right->left = newNode(5); 
    root1->right->right = newNode(4); 
    root1->left->left->left = newNode(3); 
    root1->left->left->right = newNode(2); 
    root1->left->right->left = newNode(1); 
    if (isHeap(root1)) 
        cout << "Given binary tree is a Heap\n"; 
    else 
        cout << "Given binary tree is not a Heap\n"; 
    return 0; 
}

আউটপুট

Given binary tree is a Heap