डिएप में सम्मिलन एल्गोरिदम
डिएप में एक नया तत्व डालने के लिए, हमें यह निर्धारित करना होगा कि यह मिन-हीप (लेफ्ट सबट्री) या मैक्स-हीप (राइट सबट्री) से संबंधित है, और फिर हीप गुण और क्रॉस-सबट्री कॉरेस्पॉन्डेंस को बनाए रखना होगा।
सहायक फ़ंक्शन्स: कॉरेस्पॉन्डिंग इंडेक्स गणना
// मिन-हीप में इंडेक्स m के लिए कॉरेस्पॉन्डिंग मैक्स-हीप इंडेक्स
Procedure min_value(m):
return m - 2^{floor(log2(m-1))};
// मैक्स-हीप में इंडेक्स m के लिए कॉरेस्पॉन्डिंग मिन-हीप इंडेक्स
Procedure max_value(m):
return m + 2^{floor(log2(m-1))};
सम्मिलन प्रक्रिया
Procedure deap_insertion(b[], y, m):
if (m == 1) // पहला तत्व
b[2] = y;
else {
if (m is in maximum subtree) { // नया नोड मैक्स-हीप में जा रहा है
index = min_value(m); // कॉरेस्पॉन्डिंग मिन-हीप नोड
if (y < b[index]) { // मिन-हीप गुण का उल्लंघन?
b[m] = b[index]; // मिन मान को मैक्स पोजीशन पर ले जाएं
insert y in minimum subtree; // y को मिन-हीप में डालें
} else {
insert y in maximum subtree; // सीधे मैक्स-हीप में डालें
}
} else { // नया नोड मिन-हीप में जा रहा है
index = max_value(m); // कॉरेस्पॉन्डिंग मैक्स-हीप नोड
if (y > b[index]) { // मैक्स-हीप गुण का उल्लंघन?
b[m] = b[index]; // मैक्स मान को मिन पोजीशन पर ले जाएं
insert y into maximum subtree;
} else {
insert y into minimum subtree;
}
}
}
चरण-दर-चरण तर्क
- निर्धारित करें कि नई पोजीशन `m` मिन या मैक्स सबट्री में है।
- दूसरी सबट्री में कॉरेस्पॉन्डिंग नोड ढूंढें (`min_value` या `max_value` का उपयोग करके)।
- नए मान `y` की तुलना कॉरेस्पॉन्डिंग नोड के मान से करें।
- यदि क्रॉस-सबट्री ऑर्डरिंग गुण (`min ≤ max`) का उल्लंघन होता है, तो कॉरेस्पॉन्डिंग मान को नई पोजीशन पर स्वैप करें और `y` को दूसरी सबट्री में डालें।
- अन्यथा, `y` को वर्तमान सबट्री में सामान्य हीप सम्मिलन (बबल-अप) द्वारा डालें।
जटिलता
- समय: O(log n) - ट्री की ऊंचाई के समानुपाती।
- स्पेस: O(1) अतिरिक्त।
