DAA - विधि डालें

एक तत्व को एक ढेर में सम्मिलित करने के लिए, नए तत्व को शुरू में सरणी के अंतिम तत्व के रूप में ढेर के अंत में जोड़ा जाता है।

इस तत्व को सम्मिलित करने के बाद, ढेर संपत्ति का उल्लंघन हो सकता है, इसलिए ढेर संपत्ति की मरम्मत उसके माता-पिता के साथ जोड़े गए तत्व की तुलना करके और जोड़े गए तत्व को एक स्तर तक ले जाने के लिए की जाती है, जो माता-पिता के साथ पदों की अदला-बदली करता है। इस प्रक्रिया को कहा जाता हैpercolation up

तुलना तब तक दोहराई जाती है जब तक कि माता-पिता पेरोलिंग तत्व से बड़ा या उसके बराबर न हो।

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

विश्लेषण

प्रारंभ में, सरणी के अंत में एक तत्व जोड़ा जा रहा है। यदि यह ढेर संपत्ति का उल्लंघन करता है, तो तत्व का उसके माता-पिता के साथ आदान-प्रदान किया जाता है। पेड़ की ऊंचाई हैlog n। ज्यादा से ज्यादाlog n संचालन की संख्या की आवश्यकता है।

इसलिए, इस फ़ंक्शन की जटिलता है O(log n)

उदाहरण

हमें एक अधिकतम-ढेर पर विचार करें, जैसा कि नीचे दिखाया गया है, जहां एक नए तत्व 5 को जोड़ने की आवश्यकता है।

प्रारंभ में, 55 इस सरणी के अंत में जोड़े जाएंगे।

सम्मिलन के बाद, यह ढेर संपत्ति का उल्लंघन करता है। इसलिए, तत्व को अपने माता-पिता के साथ स्वैप करना होगा। स्वैप के बाद, ढेर निम्नलिखित की तरह दिखता है।

फिर, तत्व हीप की संपत्ति का उल्लंघन करता है। इसलिए, यह अपने माता-पिता के साथ बदली है।

अब, हमें रुकना होगा।