अवधारणा
किसी दिए गए बाइनरी ट्री के संबंध में, हमें यह सत्यापित करने की आवश्यकता है कि इसमें हीप प्रॉपर्टी है या नहीं, बाइनरी ट्री को हीप होने के लिए निम्नलिखित दो शर्तों को पूरा करने की आवश्यकता है -
-
बाइनरी ट्री एक पूर्ण वृक्ष होना चाहिए (अर्थात अंतिम को छोड़कर सभी स्तर पूर्ण होने चाहिए)।
-
बाइनरी ट्री के प्रत्येक नोड का मान उसके चाइल्ड नोड से अधिक या उसके बराबर होना चाहिए (अधिकतम-हीप को ध्यान में रखते हुए)।
उदाहरण
निम्नलिखित उदाहरण के संबंध में इस पेड़ में ढेर संपत्ति है -
निम्नलिखित उदाहरण में ढेर संपत्ति नहीं है -
विधि
उपरोक्त शर्तों में से प्रत्येक को अलग से सत्यापित करना आवश्यक है, पूर्णता सत्यापित करने के लिए 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