बाइनरी हीप: ओ (एन) के निर्माण की जटिलता का प्रमाण

वास्तव में हम बाइनरी हीप और इसके निर्माण के बारे में बात करेंगे, जो कि Sift-Down (या Heapify) का उपयोग करता है। कई लोग शायद जानते हैं कि इस तरह से एक ढेर का निर्माण किया जाता है । यहाँ मैं इस तथ्य का प्रमाण देता हूँ।

पास्कल में एक सरणी पर ढेर बनाने की प्रक्रिया का एक उदाहरण यहां दिया गया है।

procedure siftdown(v:longint); var min,l,r:longint; begin l:=v*2; r:=v*2+1; min:=v; if (l <= s) and (a[l] < a[min]) then min:=l; if (r <= s) and (a[r] < a[min]) then min:=r; if min <> v then begin swap(a[min], a[v]); sift_down(min); end; end; procedure build; var i:longint; begin for i:=n downto 1 do siftdown(i); end; 

तो, चलो एक सरणी देते हैं जिसमें से एक है तत्वों, और ऑपरेटर कॉल की संख्या (प्रक्रिया में ) इस सरणी पर एक ढेर का निर्माण करते समय। जाहिर है, प्रक्रिया के परिचालन समय को निर्धारित करता है जो हमारे लिए दिलचस्प है।

लेम्मा।

कहा जाता है जब सरणी के कुछ तत्व के लिए करते हैं हो गया था ऑपरेटर कॉल करता है । तब इसका सूचकांक अधिक नहीं था ।

सबूत:

पर ऑपरेटर कॉल करता है सूची तत्व कम से कम बढ़ता है समय। अब चलो , यानी। । फिर उसके बाद हमारे पास कॉल हैं यह असंभव है, क्योंकि हमारे ढेर में तत्वों।

आइए अब मात्रा का अनुमान लगाते हैं । एक सरणी तत्व का एक सूचकांक है । मिल जाएगा ऐसा है । फिर, सूचकांक के साथ सरणी तत्व के क्रम में ढेर पर जगह में गिर गया कोई और अधिक की आवश्यकता होगी कॉल (लेम्मा द्वारा)। ऐसे सूचकांकों के साथ तत्वों की संख्या का मूल्य है जिस पर गायब हो जाती है।

इस तरह से


पर शब्द शून्य हैं (इसलिए, प्रक्रिया में चक्र के साथ शुरू कर सकते हैं )।
हम योग के प्रत्येक शब्द में बाएं कारक का अनुमान लगाते हैं



यहाँ से हमारे पास:



हम प्रत्येक राशि का मूल्यांकन करेंगे।





इस तरह से ।
एक फ़ंक्शन द्वारा ऊपर बांधा गया है । इसलिए, ।
इसलिए, प्रक्रिया का परिचालन समय एक अनुपात आनुपातिक है ।