अवधारणा
दिए गए बाइनरी ट्री के संबंध में, हमें यह सत्यापित करना होगा कि इसमें हीप गुण है या नहीं। बाइनरी ट्री को हीप होने के लिए निम्नलिखित दो शर्तों को पूरा करना होगा:
- बाइनरी ट्री एक पूर्ण ट्री होना चाहिए (यानी अंतिम स्तर को छोड़कर सभी स्तर भरे हुए हों)।
- बाइनरी ट्री के प्रत्येक नोड का मान उसके चाइल्ड नोड से बड़ा या बराबर होना चाहिए (मैक्स-हीप मानते हुए)।
उदाहरण
निम्नलिखित उदाहरण के लिए यह ट्री हीप गुण रखता है:

निम्नलिखित उदाहरण में हीप गुण नहीं है:

विधि
उपरोक्त प्रत्येक शर्त को अलग से सत्यापित करना आवश्यक है। पूर्णता के लिए isComplete फ़ंक्शन और हीप गुण के लिए isHeapUtil फ़ंक्शन लिखे गए हैं।
isHeapUtil फ़ंक्शन लिखने के लिए, हम निम्नलिखित बातों पर विचार करते हैं:
- प्रत्येक नोड के 2 बच्चे, 0 बच्चे (अंतिम स्तर के नोड्स) या 1 बच्चा हो सकता है (अधिकतम एक ऐसा नोड हो सकता है)।
- यदि नोड का कोई बच्चा नहीं है तो यह एक लीफ नोड है और सत्य लौटाता है (बेस केस)।
- यदि नोड का एक बच्चा है (यह बायां बच्चा होना चाहिए क्योंकि यह पूर्ण ट्री है) तो हमें केवल इस नोड की तुलना इसके एकल बच्चे से करनी होगी।
- यदि नोड के दोनों बच्चे हैं तो नोड पर हीप गुण की जांच करें और दोनों सबट्री के लिए पुनरावर्ती करें।
C++ कार्यान्वयन
/* 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);
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