बाइनरी मिन-हीप: कंप्लीट आकार और सुरक्षित क्रियाएँ

आप क्या सीखेंगे

बाइनरी मिन-हीप सबसे छोटी कुंजियों में से एक को रूट पर रखता है और साथ में complete बाइनरी ट्री की आकृति बनाए रखता है। इस शुरुआती पाठ में समझेंगे कि इस आकृति से शून्य-आधारित ऐरे इंडेक्स कैसे मिलते हैं और insertion तथा extract-min के बाद क्रम कैसे सुधरता है। अंत में आप ऐरे से ट्री की आकृति बना सकेंगे, हीप क्रम जाँच सकेंगे और sift-up तथा sift-down का सुरक्षित ट्रेस कर सकेंगे।

पूर्वज्ञान: साथ वाला बाइनरी ट्री की संरचना और ट्रैवर्सल का पाठ, तथा पूर्णांक ऐरे, आरंभिक मान वाला भंडारण, शर्तें, लूप, फ़ंक्शन और लौटाए गए मान। तुलना में प्रयुक्त पूर्णांक डेटा को यहाँ कुंजी कहते हैं। जब अगला चाहिए हुआ डेटा सबसे छोटी कुंजी वाला हो, जैसे प्राथमिकता कतार में, तब मिन-हीप उपयोगी है। यह डेटा-स्ट्रक्चर वाला हीप है; dynamically allocated memory के लिए इस्तेमाल होने वाला “heap” शब्द अलग संदर्भ है। यहाँ गतिशील मेमोरी आवंटन नहीं होता।

साथ में लागू होने वाले दो नियम

आकृति का नियम: आखिरी स्तर को छोड़कर सभी स्तर भरे होते हैं, और आखिरी स्तर बाएँ से दाएँ बिना अंतराल के भरता है। इसी को complete बाइनरी ट्री कहते हैं। Complete ट्री का perfect होना, यानी हर स्तर का भरा होना, जरूरी नहीं। उसका full होना, यानी हर आंतरिक नोड के ठीक दो बच्चे होना, भी जरूरी नहीं। उदाहरण के लिए छह नोड वाले complete ट्री में इंडेक्स 2 का केवल बायाँ बच्चा होता है।

क्रम का नियम: हर पैरेंट की कुंजी उसके हर मौजूद बच्चे की कुंजी से छोटी या बराबर होती है। किसी नोड से पैरेंटों की कड़ी ऊपर तक देखने पर स्पष्ट होता है कि रूट की कुंजी किसी भी रखी हुई कुंजी से बड़ी नहीं है। बराबर कुंजियाँ स्वीकार हैं। उदाहरण के लिए [2, 5, 4, 9, 7] मिन-हीप है, जबकि ऐरे में 5 के बाद 4 आता है। दोनों बच्चों का आपस में क्रम तय नहीं है। ऐरे सामान्यतः सॉर्टेड नहीं होता।

बाइनरी सर्च ट्री में किसी नोड से तुलना उसके पूरे बाएँ और दाएँ सबट्री पर पाबंदी लगाती है। मिन-हीप में ऐसी बाएँ/दाएँ विभाजन की शर्त नहीं है: दोनों बच्चे रूट से बड़े हो सकते हैं और बाएँ सबट्री की कुंजियाँ दाएँ सबट्री की कुंजियों से बड़ी या छोटी हो सकती हैं। केवल हीप नियम से यह तय नहीं होता कि कोई मनचाही कुंजी किस सबट्री में मिलेगी। बराबर प्राथमिकता वाले डेटा को पहले आया पहले निकला क्रम मिलने का वादा भी नहीं है। इस पाठ में केवल कुंजियाँ हैं; पहचान या आने का समय नहीं रखा जाता, इसलिए स्थिरता लागू नहीं होती।

Complete आकृति से ऐरे के स्थान

नोड को level order में रखें: पहले रूट, फिर उसके बच्चे बाएँ से दाएँ, फिर अगला स्तर बाएँ से दाएँ। क्षमता 7 है; count सक्रिय तत्वों की संख्या है और 0 से 7 के बीच रहता है। केवल 0 से count - 1 तक के इंडेक्स सक्रिय हैं। उनके बाद आरंभिक मान वाले स्लॉट भी अनुपयोगी भंडारण हैं, ट्री के नोड नहीं। सामान्य ट्री के मनमाने इंडेक्स-लिंक वाले निरूपण से अलग, यहाँ बच्चों के लिंक फ़ील्ड नहीं रखे जाते और सक्रिय स्थानों के बीच खाली जगह नहीं हो सकती।

सक्रिय इंडेक्स i के लिए:

• यदि i > 0 हो, पैरेंट इंडेक्स (i - 1) / 2 है; यह पूर्णांक भाग है। इंडेक्स 0 रूट है, उसका पैरेंट नहीं होता। रूट के पैरेंट को खोजने के लिए यह सूत्र न लगाएँ।
• बाएँ बच्चे का संभावित इंडेक्स 2 * i + 1 और दाएँ का 2 * i + 2 है। किसी बच्चे का डेटा तभी पढ़ें जब उसका इंडेक्स count से छोटा हो।
• इंडेक्स निकाल लेने से बच्चा मौजूद नहीं हो जाता। केवल क्षमता से तुलना सक्रिय बच्चे की जाँच नहीं है।

पाँच कुंजियों [2, 5, 4, 9, 7] में स्तर 0 पर इंडेक्स 0 में 2 है; स्तर 1 पर इंडेक्स 1 और 2 में 5 और 4 हैं; स्तर 2 पर इंडेक्स 3 और 4 में 9 और 7 हैं। स्थान 5 और 6 अनुपस्थित हैं; आखिरी स्तर अधूरा है, लेकिन बाईं ओर से लगातार भरा है। इंडेक्स 2 के संभावित बच्चे 5 और 6 सक्रिय नहीं हैं। इंडेक्स 4 का पैरेंट (4 - 1) / 2 = 1 है, क्योंकि पूर्णांक भाग में 3 को 2 से भाग देने पर 1 मिलता है। यह आकृति से निकला स्थान है, कुंजियों की तुलना नहीं।

हल किया ट्रेस 1: insertion और sift-up

इन्हीं पाँच कुंजियों से शुरू करें। 1 जोड़ने के लिए पहले इंडेक्स count = 5 पर लिखें और फिर count को 6 करें। आखिर में जोड़ने से complete आकृति बनी रहती है। अब केवल नए पत्ते से रूट की तरफ जाती कड़ी में हीप क्रम टूट सकता है।

हर अदला-बदली नई छोटी कुंजी को एक स्तर ऊपर ले जाती है। पैरेंट पहले से छोटा या बराबर हो, या कुंजी रूट तक पहुँच जाए, तो रुकें। इस प्रोग्राम में बराबर होने पर अदला-बदली नहीं होती। हीप भरा हो तो लिखने से पहले insertion असफल करें; इंडेक्स 7 मौजूद नहीं है। खाली हीप में इंडेक्स 0 पर जोड़ते हैं और ऊपर चढ़ाने की जरूरत नहीं पड़ती।

हल किया ट्रेस 2: extract-min और sift-down

Extract-min रूट की कुंजी 1 लौटाकर निकालता है। भंडारण बदलने से पहले इस कुंजी को बचाएँ। आखिरी सक्रिय स्थान हटाएँ, उसकी कुंजी 4 को रूट पर रखें और count को 6 से 5 करें। आखिरी नोड हटाने से आकृति बनी रहती है; बिना प्रतिस्थापन के रूट हटाने से बीच में खाली जगह बन जाती।

छोटा मौजूद बच्चा चुनना जरूरी है: 4 को बाएँ बच्चे 5 से बदलने पर रूट 5 हो जाएगा, जिसके नीचे 2 होगा, और हीप नियम टूटेगा। बच्चों की कुंजियाँ बराबर हों तो यह प्रोग्राम बायाँ बच्चा चुनता है। यह स्थानीय चुनाव बराबर कुंजी वाले रिकॉर्ड के स्थिर निष्कासन का वादा नहीं है। शुरू में केवल एक नोड हो तो count घटाकर शून्य हो जाता है; बची कुंजी लौटाएँ, प्रतिस्थापन या बच्चा न पढ़ें। खाली हीप से निकालना इंडेक्स 0 पढ़ने से पहले असफल होता है।

हल किया ट्रेस 3: केवल बाएँ बच्चे वाला नोड

सात कुंजियों वाले वैध हीप [1, 4, 2, 7, 8, 3, 9] से शुरू करें। 1 निकालकर आखिरी कुंजी 9 को इंडेक्स 0 पर लाएँ; छह सक्रिय कुंजियाँ [9, 4, 2, 7, 8, 3] बचती हैं। बच्चों 4 और 2 की तुलना करके इंडेक्स 2 से बदलें: [2, 4, 9, 7, 8, 3]। अब चल रहा इंडेक्स 2 है: बायाँ इंडेक्स 5 मौजूद है और उसमें 3 है; दायाँ इंडेक्स 6 count के बराबर है, इसलिए अनुपस्थित है। बाएँ बच्चे से बदलकर [2, 4, 3, 7, 8, 9] मिलता है। फिर पत्ते के इंडेक्स 5 पर रुकें। हटाने के बाद a[6] को बच्चा मानकर कभी न पढ़ें, भले ही वह भौतिक क्षमता में हो और उसमें पुराना डेटा पड़ा हो।

C का सिंटैक्स और भंडारण की शर्त

नीचे पूरे C11 प्रोग्राम में enum { CAP = 7 }; पूर्णांक स्थिरांक बनाता है। struct फ़ील्ड को एक रिकॉर्ड में जोड़ता है और typedef उस प्रकार को Heap या Result नाम देता है। Heap में ऐरे a और पूर्णांक count हैं। Result में अलग ok और value फ़ील्ड हैं। ok = 1 सफलता है; ok = 0 पर value के आरंभिक मान को अनदेखा करें। इस तरह 0, -1, INT_MIN और INT_MAX असली कुंजियाँ हो सकती हैं, विफलता का संकेत नहीं। आखिरी दो नाम author tests में <limits.h> से आते हैं और int के सबसे छोटे तथा सबसे बड़े दर्शनीय मान बताते हैं।

Heap h = {{2, 5, 4, 9, 7, 0, 0}, 5}; पहले अंदर का ऐरे, फिर फ़ील्ड क्रम से count आरंभ करता है। h.count रिकॉर्ड का फ़ील्ड चुनता है। &h जीवित रिकॉर्ड का पता है। पैरामीटर Heap *h उस रिकॉर्ड का pointer प्राप्त करता है, इसलिए उसके बदलाव caller के हीप को बदलते हैं। h->count pointer के माध्यम से फ़ील्ड चुनता है; यह (*h).count के बराबर है, जहाँ एक-ऑपरेंड * इशारा किए गए रिकॉर्ड तक पहुँचता है। 2 * i में दो-ऑपरेंड * गुणा है। const Heap *h के माध्यम से validator रिकॉर्ड पढ़ सकता है, बदल नहीं सकता। <stdio.h> से उपलब्ध NULL ऐसा null-pointer स्थिरांक है जो किसी रिकॉर्ड को इंगित नहीं करता।

Caller को NULL या एक जीवित Heap का pointer देना होगा, जिसका पूरा ऐरे और count आरंभिक मान रखता हो। Validator NULL, गलत count और टूटा क्रम पहचानता है; dangling pointer, बिना आरंभिक मान वाले ऑब्जेक्ट या मनगढ़ंत पते नहीं पहचान सकता। int a[] वाला फ़ंक्शन पैरामीटर caller के ऐरे के pointer में समायोजित होता है; पूरा ऐरे कॉपी नहीं होता। swap_values आंतरिक सहायक है: caller को दो सक्रिय इंडेक्स देने होंगे। यह कुंजियों पर जोड़-घटाव के बजाय अस्थायी चर से अदला-बदली करता है, ताकि int की सीमा पर overflow न हो।

= मान देता है; == बराबरी जाँचता है। <, >, <= पूर्णांक तुलना हैं। ! सत्यता उलटता है। || short-circuit OR है: बाईं शर्त सही हो तो दाईं नहीं जाँची जाती। && short-circuit AND है: बाईं शर्त गलत हो तो दाईं नहीं जाँची जाती। यही नियम NULL के फ़ील्ड और अनुपस्थित दाएँ बच्चे को पढ़ने से बचाते हैं। गैर-ऋणात्मक पूर्णांकों पर / भाग का भिन्नांश छोड़ देता है। if शर्त वाला खंड चुनता है; while तब तक दोहराता है जब तक शर्त अशून्य हो; while (1) से break द्वारा बाहर निकलते हैं। return फ़ंक्शन से बाहर आता है और जरूरत हो तो int या Result रिकॉर्ड का मान लौटाता है। void लौटाने वाला फ़ंक्शन कोई मान नहीं लौटाता; main में (void) का अर्थ कोई पैरामीटर नहीं है। घुँघराले कोष्ठक कथन समूह या initializer, वर्ग कोष्ठक ऐरे इंडेक्स और अर्धविराम साधारण कथन का अंत बताते हैं। i और p जैसे स्थानीय चर स्थान रखते हैं, कुंजी नहीं।

#include <stdio.h> मानक output फ़ंक्शन की घोषणा और NULL देता है। printf उद्धरण-चिह्नों की string छापता है; %d int छापता है और \n नई पंक्ति शुरू करता है। सफल प्रदर्शन पर main 0 लौटाता है, विफल प्रदर्शन पर 1। प्रोग्राम आरंभिक मान वाला निश्चित भंडारण इस्तेमाल करता है; input, allocation या recursion नहीं करता।

पूरा सीमित C11 प्रोग्राम

#include <stdio.h>

enum { CAP = 7 };

typedef struct {
    int a[CAP];
    int count;
} Heap;

typedef struct {
    int ok;
    int value;
} Result;

int valid_heap(const Heap *h) {
    if (h == NULL || h->count < 0 || h->count > CAP) {
        return 0;
    }
    int i = 1;
    while (i < h->count) {
        int p = (i - 1) / 2;
        if (h->a[p] > h->a[i]) {
            return 0;
        }
        i = i + 1;
    }
    return 1;
}

void swap_values(int a[], int x, int y) {
    int saved = a[x];
    a[x] = a[y];
    a[y] = saved;
}

int insert(Heap *h, int value) {
    if (!valid_heap(h) || h->count == CAP) {
        return 0;
    }
    int i = h->count;
    h->a[i] = value;
    h->count = h->count + 1;
    while (i > 0) {
        int p = (i - 1) / 2;
        if (h->a[p] <= h->a[i]) {
            break;
        }
        swap_values(h->a, p, i);
        i = p;
    }
    return 1;
}

Result extract_min(Heap *h) {
    Result result = {0, 0};
    if (!valid_heap(h) || h->count == 0) {
        return result;
    }
    result.ok = 1;
    result.value = h->a[0];
    h->count = h->count - 1;
    if (h->count == 0) {
        return result;
    }
    h->a[0] = h->a[h->count];
    int i = 0;
    while (1) {
        int left = 2 * i + 1;
        if (left >= h->count) {
            break;
        }
        int right = left + 1;
        int smaller = left;
        if (right < h->count && h->a[right] < h->a[left]) {
            smaller = right;
        }
        if (h->a[i] <= h->a[smaller]) {
            break;
        }
        swap_values(h->a, i, smaller);
        i = smaller;
    }
    return result;
}

int main(void) {
    Heap h = {{2, 5, 4, 9, 7, 0, 0}, 5};
    if (!insert(&h, 1)) {
        return 1;
    }
    Result first = extract_min(&h);
    if (!first.ok) {
        return 1;
    }
    printf("minimum: %d\n", first.value);
    printf("heap:");
    int i = 0;
    while (i < h.count) {
        printf(" %d", h.a[i]);
        i = i + 1;
    }
    printf("\n");
    return 0;
}

सटीक आउटपुट:

minimum: 1
heap: 2 5 4 9 7

सुरक्षा-शर्तें क्यों काम करती हैं

valid_heap पहले 0 <= count <= CAP सुनिश्चित करता है। फिर इंडेक्स 1 से शुरू करता है, इसलिए हर पैरेंट गणना पर i > 0 है, और हर सक्रिय पैरेंट-बच्चा किनारा जाँचता है। लगातार भरा prefix पहले ही complete आकृति तय कर देता है; लिंक ट्रैवर्सल की जरूरत नहीं। Short-circuit शर्तें null pointer के फ़ील्ड पढ़ने से पहले उसे अस्वीकार करती हैं। गलत इनपुट पर दोनों संक्रियाएँ कोई फ़ील्ड बदले बिना असफल होती हैं।

Insertion तभी लिखता है जब count क्षमता से कम हो। अधिकतम इंडेक्स 6 पर जोड़ सकता है और sift-up हर बार इंडेक्स 0 की ओर बढ़ता है। Extraction केवल गैर-खाली वैध हीप का रूट पढ़ता है। घटाने के बाद सकारात्मक count पुराना आखिरी इंडेक्स होता है, इसलिए प्रतिस्थापन के लिए वह पढ़ना सीमा में है। Sift-down में चल रहा इंडेक्स हमेशा सक्रिय रहता है। बच्चा पढ़ने से पहले बाएँ की मौजूदगी और दाएँ की तुलना से पहले दाएँ की मौजूदगी जाँची जाती है। हर अदला-बदली नीचे बढ़ती है और अंततः पत्ते तक पहुँचती है। क्षमता 7 में पत्ते के इंडेक्स 6 पर संभावित बायाँ इंडेक्स निकालना भी केवल 13 देता है, जो int में सुरक्षित है; वहाँ ऐरे नहीं पढ़ा जाता। यह सीमित तर्क असीमित इंडेक्स सूत्रों में overflow न होने का वादा नहीं है।

सदस्यता count से तय होती है। Extract-min के बाद पुराना आखिरी स्लॉट साफ करना जरूरी नहीं, और यह प्रोग्राम वहाँ पुराना डेटा छोड़ता है। कोई संक्रिया उसे सक्रिय नहीं मानती। तुलना में कुंजियाँ घटाई नहीं जातीं और अदला-बदली में जोड़ी नहीं जातीं, इसलिए int की चरम कुंजियाँ सुरक्षित हैं।

यहाँ O(n) सक्रिय कुंजियों की संख्या के अनुपात में बढ़ती ऊपरी सीमा बताता है, यानी रैखिक वृद्धि। O(log n) complete ट्री के स्तरों की संख्या के अनुपात वाली सीमा है: नोड संख्या दोगुनी होने पर लगभग एक अतिरिक्त स्तर। ये बढ़ने की श्रेणियाँ हैं, निर्देशों की सटीक गिनती नहीं।

सामान्य हीप एल्गोरिदम अधिकतम एक रूट-से-पत्ता पथ चलते हैं; बदलते आकार n के complete ट्री में sift का काम O(log n) है। हमारे शिक्षण फ़ंक्शन हर संक्रिया से पहले पूरा O(n) validator भी चलाते हैं, इसलिए बदलते n के हिसाब से इन फ़ंक्शन की कुल लागत O(n) है। वास्तविक निश्चित सीमा 7 होने पर हर रन स्थिर सीमा में है। पूरे रक्षात्मक फ़ंक्शन को केवल सामान्य O(log n) कहना जाँच का काम छिपा देगा। औपचारिक जटिलता प्रमाण, bottom-up heap construction और heapsort इस शुरुआती पाठ के बाहर हैं।

सीमित उपमा

सात नंबर वाली सीटें ट्री के स्तरों में लगी मानें। लोग level order में बिना खाली जगह छोड़े बैठते हैं। हर व्यक्ति एक संख्या पकड़ता है; पैरेंट सीट की संख्या उसके किसी भी भरे बच्चे की संख्या से बड़ी नहीं होनी चाहिए। नया व्यक्ति अगली खाली सीट लेता है, फिर जरूरत हो तो संख्याएँ ऊपर की ओर बदलती हैं। रूट से निकलने पर आखिरी भरी सीट की संख्या वहाँ आती है और नीचे की तुलना से क्रम सुधरता है।

उपमा केवल भरी आकृति और संख्याओं की अदला-बदली समझाती है। लोग pointer नहीं हैं, खाली सीटें नोड नहीं हैं, और बराबर प्राथमिकता वाले रिकॉर्ड बदलने से किसी व्यक्ति के पहले निकलने का वादा नहीं बनता। कोड में कुंजियाँ चलती हैं; इंडेक्स के संबंध स्थिर रहते हैं।

मुख्य बातें

• बाइनरी मिन-हीप में complete आकृति और पैरेंट <= बच्चा, दोनों जरूरी हैं।
• Count सकारात्मक हो तो रूट इंडेक्स 0 पर न्यूनतम कुंजी मिलती है।
• (i - 1) / 2 केवल i > 0 पर लगाएँ; बच्चों के इंडेक्स count से जाँचें।
• आखिर में जोड़कर ऊपर सुधारें; रूट बचाकर आखिरी से बदलें, फिर छोटे मौजूद बच्चे के साथ नीचे सुधारें।
• दोहराई कुंजियाँ वैध हैं; सॉर्टेड ऐरे या बराबर कुंजियों का स्थिर क्रम नहीं मिलता।
• स्थिति और डेटा अलग हैं। भरे में जोड़ना और खाली से निकालना, ऐरे पहुँचने से पहले सँभालें।

दो अतिरिक्त अभ्यास

1. [2, 5, 4, 9, 7] में 3 जोड़ें। उत्तर से पहले ट्रेस करें। इंडेक्स 5 पर जोड़ने से [2, 5, 4, 9, 7, 3] मिलता है। पैरेंट 2 में 4 है, इसलिए बदलकर [2, 5, 3, 9, 7, 4] होता है। पैरेंट 0 में 2 <= 3 है, इसलिए रुकें; count 6 है।
2. आरंभिक मान वाले खाली हीप में दो बार 0 जोड़ें, फिर तीन बार निकालें। दोनों insertion सफल हैं; दूसरी बराबर कुंजी इंडेक्स 1 पर रहती है। परिणाम {1, 0}, {1, 0}, फिर {0, 0} हैं। केवल पहले दो value वैध डेटा हैं। आखिरी count 0 है। दो एक-जैसी कुंजियों से स्थिर क्रम का निष्कर्ष नहीं निकाल सकते।

सीमा और अगला कदम

यह GATE CS डेटा-स्ट्रक्चर का शुरुआती सेतु है। इसमें heapsort, heap construction के प्रमाण, सभी priority queue निरूपण या पूरा पाठ्यक्रम नहीं पढ़ाया गया है। नीचे के प्रश्न मौलिक अभ्यास हैं, पिछले वर्षों के प्रश्न नहीं। किसी कोर्स का परीक्षा-वर्ष बदलने का दावा नहीं है। हिंदी सीखने में सहायता है, GATE CS का आधिकारिक हिंदी प्रश्नपत्र होने का दावा नहीं।

छह मौलिक एक-सही-विकल्प प्रश्न

1. लगातार भरे शून्य-आधारित हीप में count = 6 और क्षमता 7 है। इंडेक्स 2 के कौन-से बच्चे सक्रिय हैं?

A. इंडेक्स 5 और 6 दोनों B. केवल बायाँ बच्चा इंडेक्स 5 C. केवल दायाँ बच्चा इंडेक्स 6 D. कोई बच्चा नहीं

2. सक्रिय ऐरे [2, 9, 3] के बारे में कौन-सा कथन सही है?

A. यह अवैध है क्योंकि बायाँ बच्चा दाएँ से बड़ा है। B. यह मिन-हीप है, इसलिए 9 की खोज में BST का बाएँ/दाएँ विभाजन लागू होगा। C. यह मिन-हीप है, इसलिए इसका ऐरे गैर-घटते क्रम में सॉर्टेड है। D. यह मिन-हीप है: दोनों बच्चे कम-से-कम 2 हैं और बच्चों के आपसी क्रम की शर्त नहीं है।

3. पाठ के एल्गोरिदम से [3, 6, 5, 9] में 1 जोड़ें। अंतिम सक्रिय ऐरे क्या है?

A. [1, 3, 5, 9, 6] B. [1, 3, 5, 6, 9] C. [3, 1, 5, 9, 6] D. [3, 6, 5, 9, 1]

4. पाठ के एल्गोरिदम से [1, 4, 2, 7, 8, 3, 9] से एक बार न्यूनतम निकालें। अंतिम सक्रिय ऐरे कौन-सा है?

A. [4, 7, 2, 9, 8, 3] B. [2, 4, 9, 7, 8, 3] C. [2, 4, 3, 7, 8, 9] D. [1, 4, 2, 7, 8, 3]

5. एक वैध Heap में count = CAP = 7 है। दिए कोड में insert(&h, -1) क्या करता है?

A. -1 की प्राथमिकता अधिक होने से रूट को बदल देता है। B. 0 लौटाता है और count या किसी ऐरे स्लॉट को नहीं बदलता। C. इंडेक्स 7 पर -1 लिखकर ऊपर सुधारता है। D. 1 लौटाता है लेकिन चुपचाप एक सबसे बड़ी कुंजी हटा देता है।

6. वैध एक-तत्व हीप में INT_MIN है। extract_min क्या लौटाता है और नया count क्या होगा?

A. {0, 0}, count 1, क्योंकि INT_MIN विफलता का संकेत है। B. {1, 0}, count 0, क्योंकि आखिरी कुंजी निकालने पर उसका मान साफ हो जाता है। C. {1, INT_MIN}, count 1, क्योंकि extraction केवल पढ़ता है, हटाता नहीं। D. {1, INT_MIN}, count 0, बिना प्रतिस्थापन या बच्चे को पढ़े।

विकल्पों के समझाए गए उत्तर

1. B

A गलत है: 6 count के बराबर है, इसलिए क्षमता में होने पर भी अनुपयोगी है।

B सही है: बायाँ = 2 * 2 + 1 = 5 < 6; दायाँ = 6, 6 से छोटा नहीं है।

C गलत है: इंडेक्स 6 अनुपस्थित है; बाएँ से भरी आकृति मौजूद इंडेक्स 5 को छोड़ नहीं सकती।

D गलत है: इंडेक्स 5 सक्रिय है और इंडेक्स 2 का बायाँ बच्चा है।

2. D

A गलत है: 9 > 3 स्वीकार है; हीप क्रम पैरेंट की तुलना हर बच्चे से करता है।

B गलत है: हीप BST वाला सबट्री विभाजन नहीं देता; यहाँ बायाँ बच्चा 9 रूट 2 से बड़ा है।

C गलत है: 9 के बाद 3 आना घटता क्रम है, इसलिए यह वैध हीप सॉर्टेड ऐरे नहीं है।

D सही है: स्थान 0, 1, 2 complete आकृति देते हैं और जरूरी तुलनाएँ 2 <= 9 तथा 2 <= 3 हैं।

3. A

A सही है: 4 पर जोड़ें, पैरेंट 1 की कुंजी 6 से और फिर पैरेंट 0 की कुंजी 3 से बदलें; [1, 3, 5, 9, 6] मिलता है।

B इस एल्गोरिदम के लिए गलत है: यह वैध हीप है, लेकिन इसमें बच्चे 9 और 6 भी आपस में बदले गए हैं, जो sift-up नहीं करता।

C गलत है: यह एक अदला-बदली के बाद की स्थिति है; पैरेंट 3 अब भी बच्चे 1 से बड़ा है।

D गलत है: इसमें केवल आखिर में जोड़ा गया है; कुंजी 1 पैरेंट 6 के नीचे है और हीप क्रम टूटा है।

4. C

A गलत है: हमेशा बायाँ बच्चा चुनने से रूट 4 बच्चे 2 से ऊपर रह जाता है; छोटा मौजूद बच्चा चुनना जरूरी है।

B गलत है: पहली अदला-बदली हुई है, लेकिन इंडेक्स 2 की कुंजी 9 अपने अकेले बच्चे इंडेक्स 5 की कुंजी 3 से बड़ी है।

C सही है: 1 बचाएँ, 9 रूट पर लाएँ, इंडेक्स 2 की कुंजी 2 से और फिर उसके बाएँ बच्चे इंडेक्स 5 की कुंजी 3 से बदलें।

D गलत है: केवल आखिरी स्थान हटाया गया है; न्यूनतम 1 अभी भी मौजूद है।

5. B

A गलत है: प्रस्तावित कुंजी कुछ भी हो, क्षमता की शर्त किसी लेखन से पहले लौटा देती है।

B सही है: valid_heap केवल पढ़ता है; count == CAP होने पर जोड़ने या बदलने से पहले 0 लौटता है।

C गलत है: सात तत्वों के ऐरे में इंडेक्स 0 से 6 हैं; सुरक्षा-शर्त सीमा के बाहर लेखन रोकती है।

D गलत है: इस insertion में पुरानी कुंजी बदलने की नीति नहीं है; भरा हीप संक्रिया अस्वीकार करता है।

6. D

A गलत है: किसी int कुंजी को विफलता संकेत के लिए आरक्षित नहीं किया गया; विफलता ok = 0 से बताई जाती है।

B गलत है: count बदलने से पहले रूट बचता है, इसलिए लौटता डेटा INT_MIN है, शून्य नहीं।

C गलत है: extract_min count घटाकर अकेला सक्रिय तत्व निकालता है।

D सही है: ok 1 बनता है, रूट की कुंजी कॉपी होती है, count 0 हो जाता है और तुरंत लौटने से प्रतिस्थापन नहीं पढ़ा जाता।