एक हीप पेड़ में के-वें तत्व

Question

मेरे पास एक ढेर है (एक बाइनरी पेड़ की तरह लागू किया गया है: प्रत्येक नोड में बच्चों के लिए दो पॉइंटर्स और माता-पिता के लिए एक पॉइंटर होता है)।

मैं इसमें तत्वों की संख्या के कारण के-वें तत्व (बीएफएस आदेश में) कैसे पा सकता हूं? मुझे लगता है कि यह ओ (लॉगन) समय में किया जा सकता है ..

Answer 1

(मुझे "केएच तत्व (बीएफएस ऑर्डर में)" का मानना ​​है कि आप का अर्थ तत्व शीर्ष से नीचे के परिप्रेक्ष्य से है , इनपुट के बाएं से दाएं स्कैन।)

चूंकि आप जानते हैं कि एक बाइनरी ढेर एक पूर्ण बाइनरी पेड़ है (संभवतः अंतिम स्तर पर छोड़कर), आप जानते हैं कि पेड़ का आकार एक आदर्श बाइनरी पेड़ है कुछ ऊंचाई (जिसमें 2 ^के कुछ के लिए नोड्स शामिल हैं) बाएं से दाएं से भरे कुछ नोड्स के साथ। इन वृक्षों का एक वास्तव में निफ्टी संपत्ति तब होता है जब आप एक तस्वीर में नोड्स की संख्या को लिखने, एक अनुक्रमण मान:

     1 
      2    3 
     4  5  6  7 
     8 9 10 11 12 13 14 15 

ध्यान दें कि प्रत्येक परत एक नोड दो की एक शक्ति है कि के साथ शुरू होता है। तो चलो लगता है, परिकल्पित करते हैं, कि तुम संख्या 13. कोई 13 से 8 अधिक से अधिक दो की सबसे बड़ी शक्ति को देखने के लिए चाहता था, इसलिए हम जानते हैं कि 13 पंक्ति में दिखाई देना चाहिए

8 9 10 11 12 13 14 15 

अब हम इस का उपयोग कर सकते 13 बैक से पेड़ की जड़ तक पथ को उलटा करने के लिए ज्ञान। हम जानते हैं, उदाहरण के लिए, यह 13 इस पंक्ति में संख्याओं के उत्तरार्ध में है, जिसका अर्थ है कि 13 रूट के दाहिनी उप-धारा से संबंधित है (यदि यह बाएं उपट्री से संबंधित है, तो हम उपट्री में होंगे 8, 9, 10, और 11) इसका मतलब यह है कि हम जड़ से सही जाने के लिए और संख्या के आधे से बाहर फेंक पाने के लिए

12 13 14 15 

हम एक वृक्ष के नोड 3 पर अब कर रहे हैं कर सकते हैं। तो क्या हम बाएं या दाएं जाते हैं? खैर, 13 इन संख्याओं के पहले भाग में है, इसलिए हम इस बिंदु पर जानते हैं कि हमें नोड 3 के बाएं उपट्री में उतरने की जरूरत है। यह हमें 6 नोड करने के लिए ले जाता है, और अब हम पहले छमाही के साथ छोड़ दिए गए हैं संख्या:

12 13 

13 इन नोड्स के आधे दाएं भाग में है, इसलिए हम सही करने के लिए उतरना चाहिए, हमें लेने 13. और देखा नोड के लिए! वहाँ थे!

तो यह प्रक्रिया कैसे काम करती है? खैर, वास्तव में एक बहुत ही प्यारा चाल है जिसका हम उपयोग कर सकते हैं।

     0001 
      0010     0011 
     0100  0101  0110  0111 
    1000 1001 1010 1011 1100 1101 1110 1111 
           ^^^^ 

मैं नोड 13. के स्थान हमारा एल्गोरिदम निम्नलिखित तरीके से काम किया बताया गया है::

1. परत युक्त खोजें की एक ही पेड़ हम ऊपर था, लेकिन बाइनरी में बाहर लिखते हैं नोड
2. सवाल में नोड पर नहीं जबकि:
   1. नोड परत क्या है की पहली छमाही में है, तो छोड़ दिया और दूर रेंज के आधे दाएं भाग फेंक ले।
   2. यदि नोड परत के दूसरे भाग में है, तो इसमें है, दाएं स्थानांतरित करें और सीमा के बाएं आधे भाग को फेंक दें।

क्या इस बाइनरी में अर्थ के बारे में सोचते हैं।नोड युक्त परत ढूंढना में सबसे महत्वपूर्ण बिट सेट खोजने के बराबर है। 13 में, जिसमें द्विआधारी प्रतिनिधित्व 1101 है, एमएसबी 8 बिट है। इसका मतलब है कि हम आठ से शुरू होने वाली परत में हैं।

तो हम कैसे निर्धारित करते हैं कि हम बाएं उपट्री या दाएं उपट्री में हैं या नहीं? खैर, ऐसा करने के लिए, हमें यह देखना होगा कि क्या हम इस परत के पहले भाग में हैं या दूसरे छमाही में हैं। और अब एक प्यारा चाल के लिए - एमएसबी के बाद अगली बिट देखें। यदि यह बिट 0 पर सेट है, तो हम सीमा के पहले भाग में हैं, और अन्यथा हम सीमा के दूसरे भाग में हैं। इस प्रकार हम निर्धारित कर सकते हैं कि हम किस सीमा का हिस्सा केवल अगले नंबर को देखकर कर रहे हैं! इसका मतलब यह है कि हम निर्धारित कर सकते हैं कि संख्या के अगले भाग को देखकर कौन सा उपखंड उतरना है।

एक बार हमने ऐसा करने के बाद, हम केवल इस प्रक्रिया को दोहरा सकते हैं। हम अगले स्तर पर क्या करते हैं? खैर, अगर अगली बिट शून्य है, तो हम बाएं जाते हैं, और यदि अगली बिट एक है, तो हम सही हो जाते हैं। क्या यह 13 के लिए इसका मतलब है पर एक नज़र डालें:

1101 
    ^^^ 
    ||| 
    ||+--- Go right at the third node. 
    || 
    |+---- Go left at the second node. 
    | 
    +----- Go right at the first node. 

दूसरे शब्दों में, हम सिर्फ MSB के बाद संख्या के टुकड़े को देखकर सवाल में हमारे नोड के लिए पेड़ की जड़ से पथ उल्लेख कर सकते हैं !

क्या यह हमेशा काम करता है! बिलकुल! आइए नंबर 7 आज़माएं। इसमें द्विआधारी प्रतिनिधित्व 0111 है। एमएसबी 4 की जगह में है। हमारे एल्गोरिदम का उपयोग करके, हम यह करेंगे:

0111 
    ^^ 
    || 
    |+--- Go right at the second node. 
    | 
    +---- Go right at the first node. 

हमारी मूल तस्वीर में देखना, यह सही तरीका है!

यहाँ कुछ किसी न किसी तरह सी है/इस एल्गोरिथ्म के लिए सी ++ स्यूडोकोड:

Node* NthNode(Node* root, int n) { 
    /* Find the largest power of two no greater than n. */ 
    int bitIndex = 0; 
    while (true) { 
     /* See if the next power of two is greater than n. */ 
     if (1 << (bitIndex + 1) > n) break; 
     bitIndex++; 
    } 

    /* Back off the bit index by one. We're going to use this to find the 
    * path down. 
    */ 
    bitIndex--; 

    /* Read off the directions to take from the bits of n. */ 
    for (; bitIndex >= 0; bitIndex--) { 
     int mask = (1 << bitIndex); 
     if (n & mask) 
      root = root->right; 
     else 
      root = root->left; 
    } 
    return root; 
} 

मैं इस कोड का परीक्षण नहीं किया! डॉन नूथ को पैराफ्रेश करने के लिए, मैंने अभी दिखाया है कि अवधारणात्मक रूप से यह सही काम करता है। मेरे यहां एक-एक-एक त्रुटि हो सकती है।

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

आशा है कि इससे मदद मिलती है!