हटाए जाने और हटाने के बीच डेटा बदलते समय आइटम को हटाकर

Question

मैंने कल एक प्रश्न पूछा लेकिन यह बहुत स्पष्ट नहीं था इसलिए यह एक और विशिष्ट सवाल है।

मैं एक सरणी के रूप में अपने minheap का प्रतिनिधित्व कर रहा हूँ। मुझे लगता है कि मुझे लगता है कि minheaps की अच्छी समझ है, लेकिन मैं एक निश्चित अवधारणा के भीतर अस्पष्ट हूँ। मिन्हैप्स हमेशा रूट के रूप में सबसे छोटा नोड होना चाहिए। मान को हटाने के लिए, रूट सरणी प्रस्तुति (एक पत्ता नोड) में अंतिम तत्व पर सेट है और सरणी का आकार घट गया है। रूट नोड को तब siftDown/PercolateDown या जो भी आप इसे कॉल करना चाहते हैं, का उपयोग करके सही ढंग से रखा जाता है। यह बहुत कुशल है। उदाहरण के लिए:

यहाँ 29 पिछले तत्व से लिया गया है और siftDown (1) यह जगह देगा:

1. 29 15 और 38. के ​​साथ तुलना की जाती है एक्सचेंज 29 और 15.
2. 2 की तुलना 25 और 20 के साथ की जाती है। एक्सचेंज 2 9 और 20.
3. 2 की तुलना 30, 2 9 < 30 से की जाती है इसलिए हम कर रहे हैं।

यह सब ठीक है और अच्छा है, लेकिन क्या होगा यदि मिनट को हटाने के 2 उदाहरणों के बीच में, कुछ अन्य डेटा बदलते हैं?

यहाँ है, तो: उदाहरण के लिए:

1. 29 15 और 38. के ​​साथ तुलना की जाती है एक्सचेंज 29 और 15.
2. 29 30 और 32. 29 < 30 और से की जाती है 29 < 32 इसलिए हम कर रहे हैं।

1 पेड़ में सबसे छोटा मूल्य है, लेकिन इसे न्यूनतम, 15 के रूप में सेट नहीं किया गया है। यह मेरे लिए एक बड़ा मुद्दा है। मैं डिजस्ट्रस एल्गोरिदम को लागू करने की कोशिश कर रहा हूं, मैं कक्षाओं में बने जावा को छूए बिना अपने स्वयं के डेटा संरचनाओं का उपयोग करने की भी कोशिश कर रहा हूं।

तो मेरी समस्या के लिए अधिक प्रासंगिक उदाहरण होगा:

Dijkstras से परिचित लोगों के लिए, 99 अनन्तता की एक अस्थायी दूरी का प्रतिनिधित्व करता है और अन्य संख्या ग्राफ नोड्स जो अगले दौरा किया जाना चाहिए प्रतिनिधित्व करते हैं (छोटी सी दूरी के साथ नोड, इस मामले में 3)।

हर बार जब मैं मिनट निकालता हूं तो पेड़ को पुनर्निर्माण करना एक समाधान है, हालांकि इसका मतलब है कि एक मिनीहेप की शक्ति खो जाती है और कोई भी कार्यान्वयन क्रॉल में धीमा हो जाता है।

क्षमा करें अगर मैं इसे ठीक से समझ नहीं पा रहा हूं लेकिन मैं दिनों से इसके साथ अटक गया हूं और मुझे वास्तव में कुछ मदद चाहिए।

Answer 1

आपको एल्गोरिदम की पूर्व शर्त को समझने की आवश्यकता है। एल्गोरिदम siftDown किसी भी मनमाने ढंग से सरणी के लिए काम नहीं करता है। यह केवल तब काम करता है जब उसके बाएं बच्चे और दाहिने बच्चे ढेर होते हैं।

आपके दूसरे उदाहरण में, रूट का बायां बच्चा एक न्यूनतम ढेर नहीं है। तो, एल्गोरिदम एक न्यूनतम ढेर का उत्पादन नहीं करेगा।

वहाँ अगर तुम एक सरणी है कि ढेर संपत्ति का उल्लंघन करती है में समाप्त, छवि नंबर की तरह अपने कार्यान्वयन में कुछ गड़बड़ होना चाहिए 3.