ধারণা
একটি প্রদত্ত বাইনারি গাছের ক্ষেত্রে, আমাদের এটির হিপ প্রপার্টি আছে কি না তা যাচাই করতে হবে, বাইনারি ট্রিকে হিপ হওয়ার জন্য নিম্নলিখিত দুটি শর্ত পূরণ করতে হবে –
-
বাইনারি ট্রি একটি সম্পূর্ণ গাছ হওয়া উচিত (অর্থাৎ শেষ ব্যতীত সমস্ত স্তর পূর্ণ হওয়া উচিত)।
-
বাইনারি ট্রির প্রতিটি নোডের মান তার চাইল্ড নোডের চেয়ে বেশি বা সমান হওয়া উচিত (ম্যাক্স-হিপ বিবেচনা করে)।
উদাহরণ
নিম্নোক্ত উদাহরণের ক্ষেত্রে এই গাছে রয়েছে হিপ প্রপার্টি –
নিম্নলিখিত উদাহরণে হিপ প্রপার্টি নেই –
পদ্ধতি
সম্পূর্ণতা যাচাই করার জন্য উপরের প্রতিটি শর্তকে আলাদাভাবে যাচাই করতে হবে isComplete(এই ফাংশনটি পরীক্ষা করে যে বাইনারি ট্রি সম্পূর্ণ হয়েছে কি না) এবং হিপ যাচাই করার জন্য isHeapUtil ফাংশন লেখা আছে।
isHeapUtil ফাংশন লেখার ক্ষেত্রে, আমরা নিম্নলিখিত বিষয়গুলি বিবেচনা করি –
-
প্রতিটি নোডে 2টি শিশু, 0টি শিশু (শেষ স্তরের নোড) বা 1টি শিশু (সেখানে সর্বাধিক একটি নোড থাকতে পারে) থাকতে পারে।
-
যদি দেখা যায় যে নোডের কোন সন্তান নেই তবে এটি একটি লিফ নোড এবং সত্য (বেস কেস) ফিরে আসে
-
যদি দেখা যায় যে নোডের একটি সন্তান আছে (এটিকে অবশ্যই শিশু রেখে যেতে হবে কারণ এটি একটি সম্পূর্ণ গাছ) তাহলে আমাদের এই নোডটিকে শুধুমাত্র তার একক সন্তানের সাথে তুলনা করতে হবে।
-
যদি দেখা যায় যে নোডের উভয় সন্তান আছে তাহলে উভয় সাবট্রির জন্য নোডে রিকারে হিপ প্রপার্টি যাচাই করুন।
উদাহরণ
/* C++ program to checks if a binary tree is max heap or not */
#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);
// Recur for left and right subtrees
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;
}
// Driver program
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
