बाइनरी मिन ढेर

Question

में सम्मिलित करना तत्वों मैं आइटम डालने रहा हैं: एक के बाद एक आइटम एक द्विआधारी मिनट ढेर में 10,12,14,1,6 कैसे परिणाम कैसा दिखेगा, मेरी समस्या निम्नलिखित

साथ है जब मैं शुरू मेरे पास है:

10 

तो

10 
/
12 

तो

10 
/\ 
12 14 

तो

1 
/\ 
10 14 
/
12 

लेकिन यह नहीं ठीक है, तो यह है कि ऐसा करने के लिए सही तरीके से क्या है?

नोट: यह एक होमवर्क प्रश्न है, यदि आप इस सवाल को हल करने में सहज महसूस नहीं करते हैं, तो यह अवधारणा को समझने की कोशिश कर रहा है (यह वैसे भी पूरा सवाल नहीं है) कृपया इसी तरह के मुद्दे के साथ एक उदाहरण प्रदान करें।

Answer 1

आपको एक ही बच्चे (या बिल्कुल पत्ती के रूप में) के रूप में नया तत्व जोड़ना है (रूट के रूप में नहीं), इसका मतलब है कि आप इसे पहले "दाएं" मुक्त स्थान में डालते हैं (या अपने हीप-सरणी में, बस अतं मै)।

फिर आपको ढेर की स्थिति को फिर से स्थापित करना होगा, इसे "हेपफीइफ़" कहा जाता है। यह दो चरणों में होता है: जब तक यह माता-पिता से छोटा होता है और यह जड़ नहीं है अपनी मूल नोड के साथ:

1. बार बार नए तत्व (तत्व यह है कि ढेर शर्तों का उल्लंघन सामान्य) का आदान-प्रदान।
2. नए तत्व को छोटे मूल्य के साथ बच्चे के साथ दोहराएं, जब तक कि नया तत्व छुट्टी न हो या दोनों बच्चे नोड तत्व से भी बड़े हों।

इसका मतलब है कि

10 
/\ 
12 14 

+ 1

10 
/\ 
12 14 
/
1 

पर ले जाया जाता और इसलिए आप

10 
/\ 
    1 14 
/
12 

heapify करने के लिए है लेकिन यह अभी भी नहीं है कि ढेर शर्तों का उल्लंघन, ठीक है, तो आपको फिर से

को तेज़ करना होगा

 1 
/\ 
10 14 
/
12 

और वहाँ आप कर रहे हैं ... सब कुछ ठीक अब :-)

Answer 2

step1:  10 
step2:  10 
     /
     12 
step3:  10 
     /\ 
     12 14 
step4:  1 
     /\ 
     10 12 
     /
     14 
step5:  1 
     /\ 
     6 10 
     /\ 
     12 14