स्टोर संख्या

Question

निम्न समस्या को देखते हुए की एक धारा से सबसे बड़ी 5000 संख्या:

"संख्या की एक धारा से सबसे बड़ी 5000 नंबर स्टोर"

समाधान जो दिमाग में स्प्रिंग्स एक है पेड़ में नोड्स की संख्या की गिनती बनाए रखने के लिए बाइनरी सर्च पेड़ और 5000 तक पहुंचने के बाद सबसे छोटे नोड का संदर्भ। जब गिनती 5000 तक पहुंच जाती है, तो जोड़ने के लिए प्रत्येक नई संख्या की तुलना पेड़ में सबसे छोटी वस्तु से की जा सकती है। यदि अधिक हो, तो नया नंबर जोड़ा जा सकता है, फिर सबसे छोटा हटा दिया जाता है और नई छोटी गणना की जाती है (जो पहले से ही सबसे छोटी होनी चाहिए)।

इस समाधान के साथ मेरी चिंता यह है कि बाइनरी पेड़ स्वाभाविक रूप से स्क्व्यूड होने जा रहा है (क्योंकि मैं केवल एक तरफ हट रहा हूं)।

क्या इस समस्या को हल करने का कोई तरीका है जो एक बहुत ही खराब पेड़ नहीं बनाएगा?

मामले में किसी को भी यह चाहता है, मैंने सम्मिलित कर दिया छद्म कोड मेरा समाधान अब तक नीचे के लिए:

process(number) 
{ 
    if (count == 5000 && number > smallest.Value) 
    { 
    addNode(root, number) 
    smallest = deleteNodeAndGetNewSmallest (root, smallest) 
    } 
} 

deleteNodeAndGetNewSmallest(lastSmallest) 
{ 
    if (lastSmallest has parent) 
    { 
    if (lastSmallest has right child) 
    { 
     smallest = getMin(lastSmallest.right) 
     lastSmallest.parent.right = lastSmallest.right 
    } 
    else 
    { 
     smallest = lastSmallest.parent 
    } 
    } 
    else 
    { 
    smallest = getMin(lastSmallest.right) 
    root = lastSmallest.right 
    } 
    count-- 
    return smallest 
} 

getMin(node) 
{ 
    if (node has left) 
    return getMin(node.left) 
    else 
    return node 
} 

add(number) 
{ 
    //standard implementation of add for BST 
    count++ 
} 

Answer 1

इस के लिए सरल समाधान के अधिकतम आकार के एक मिनट heap को बनाए रखने है 5000

• प्रत्येक बार जब कोई नया नंबर आता है - जांच करें कि ढेर छोटा है तो 5000, यदि यह है - इसे जोड़ें।
• यदि यह नहीं है - तो जांचें कि न्यूनतम छोटा है तो नया तत्व, और यदि यह है, तो इसे पॉप करें और इसके बजाय नया तत्व डालें।
• जब आप पूरा कर लेंगे - आपके पास 5000 सबसे बड़े तत्व युक्त ढेर है।

यह समाधान, O(nlogk) जटिलता है जहां n तत्वों की संख्या है और k तत्वों की जरूरत है (5000 आपके मामले में) की संख्या है।

यह में भी selection algorithm का उपयोग करके किया जा सकता है - सभी तत्वों को स्टोर करें, और फिर 5001 वां सबसे बड़ा तत्व ढूंढें, और इससे सबकुछ बड़ा करें। लेकिन इसे लागू करना कठिन है और उचित आकार इनपुट के लिए - बेहतर नहीं हो सकता है। साथ ही, यदि स्ट्रीम में डुप्लीकेट होते हैं, तो अधिक प्रोसेसिंग की आवश्यकता होती है।

Answer 2

एक (न्यूनतम) प्राथमिकता कतार का उपयोग करें। प्रत्येक आने वाली वस्तु को कतार में जोड़ें और जब आकार 5000 तक पहुंचता है तो हर बार जब आप आने वाले तत्व को जोड़ते हैं तो न्यूनतम (शीर्ष) तत्व हटा दें। कतार में 5,000 सबसे बड़े तत्व होंगे और जब इनपुट बंद हो जाए, तो बस सामग्री को हटा दें। इस MinPQ को एक ढेर भी कहा जाता है लेकिन यह एक अधिभारित शब्द है। सम्मिलन और विलोपन लॉग 2 (एन) के बारे में लेते हैं। जहां एन 5000 पर अधिकतम हो जाता है, यह 12 से अधिक होगा [log2 (4096) = 12] आपके द्वारा प्रसंस्करण की जा रही वस्तुओं की संख्या।

रॉबर्ट सेडगेविक और केविन वेन द्वारा जानकारी का एक उत्कृष्ट स्रोत एल्गोरिदम, (चौथा संस्करण) है। Coursera.org पर एक उत्कृष्ट एमओयूसी है जो इस पाठ पर आधारित है।