View source for हीपसॉर्ट

{{Short description|A sorting algorithm which uses the heap data structure}}

{{Infobox Algorithm|class=[[Sorting algorithm]]
|image=[[File:Sorting heapsort anim.gif]]
|caption=हीपसॉर्ट के द्वारा एक यादृच्छिक रूप से विकल्पित मूल्यों के एक एरे को क्रमबद्ध करने की एक रन। एल्गोरिदम के पहले चरण में, एरे के तत्वों को हीप संपत्ति को पूरा करने के लिए पुनः क्रमित किया जाता है। वास्तविक क्रमबद्धीकरण से पहले, चित्रण के लिए हीप ट्री संरचना का संक्षेपण दिखाया जाता है, यह केवल विवरण के लिए है।
|data=[[Array data structure|Array]]
|time=<math>O(n\log n)</math>
|average-time=<math>O(n\log n)</math>
|best-time=<math>O(n\log n)</math> (distinct keys)<br />or <math>O(n)</math> (equal keys)
|space=<math>O(n)</math> total <math>O(1)</math> auxiliary
}}
[[कंप्यूटर विज्ञान]] में, हीपसॉर्ट एक तुलना-आधारित क्रमबद्धीकरण [[छँटाई एल्गोरिथ्म|कलन विधि]] है। हीपसॉर्ट को सुधारित सिलेक्शन सॉर्ट के रूप में समझा जा सकता है: चयन सॉर्ट की तरह, हीपसॉर्ट अपने इनपुट को एक क्रमबद्ध और अक्रमबद्ध क्षेत्र में विभाजित करता है और यह अक्रमबद्ध क्षेत्र सतत रूप से क्षेत्र को कम करके बढ़ाता है जिसमें से सबसे बड़ा तत्व निकालकर उसे क्रमबद्ध क्षेत्र में सम्मिलित करता है। इसके विपरीत, हीपसॉर्ट अप्रयुक्त क्षेत्र का रैखिक समय स्कैन के साथ समय व्यर्थ नहीं करता है; बल्कि, हीपसॉर्ट अप्रयुक्त क्षेत्र को हीप डेटा संरचना में बनाए रखकर प्रत्येक स्टेप में सबसे बड़े तत्व को तेजी से खोजने में सहायता करता है।<ref>{{cite book |first=Steven |last=Skiena |author-link=Steven Skiena |title=एल्गोरिथम डिज़ाइन मैनुअल|publisher=Springer |year=2008 |page=109 |chapter=Searching and Sorting |isbn=978-1-84800-069-8 |quote=[H]eapsort is nothing but an implementation of selection sort using the right data structure. |doi=10.1007/978-1-84800-070-4_4}}<!--DOI for chapter--></ref>

यद्यपि बहुत से यंत्रों पर अच्छी तरह से लागू किए गए क्विकसॉर्ट से कुछ धीमा होता है, हीपसॉर्ट का लाभ एक अधिक सकारात्मक वर्स्ट-केस {{math|[[big O notation|O(''n'' log ''n'')]]}}  कार्यावधि है और इसलिए इंट्रोसॉर्ट द्वारा इसका उपयोग क्विकसॉर्ट अपरिचित एवं प्रतिकूलता होने पर पुनर्प्राप्ति के रूप में किया जाता है। हीपसॉर्ट एक स्थान में [[इन-प्लेस एल्गोरिदम|कलन विधि]] है, परंतु यह एक स्थिर सॉर्ट नहीं है।

हीपसॉर्ट का आविष्कार 1964 मेंजे. डब्ल्यू. जे. विलियम्स द्वारा आविष्कृत किया गया था। इससे पहले भी विलियम्स ने हीप को एक उपयुक्त डेटा संरचना के रूप में प्रस्तुत किया था। उसी साल में, रॉबर्ट डब्ल्यू. फ्लॉयड ने एक सुधारित संस्करण प्रकाशित किया था जो किसी सारणी को प्लेस में सॉर्ट कर सकता था, जो उनके पहले ट्रीसॉर्ट [[इन-प्लेस एल्गोरिदम|कलन विधि]] के अध्ययन को जारी रखा गया।<ref name="brass">{{cite book |first=Peter |last=Brass |title=उन्नत डेटा संरचनाएँ|publisher=Cambridge University Press |year=2008 |isbn=978-0-521-88037-4 |page=209}}</ref>



== अवलोकन ==
हीपसॉर्ट कलन-विधि को दो भागों में विभाजित किया जा सकता है।

पहले चरण में, डेटा से हीप बनाया जाता है। हीप प्रायः पूर्ण बाइनरी ट्री विन्यास के साथ एक सारणी में रखा जाता है। संपूर्ण बाइनरी ट्री, बाइनरी ट्री संरचना को सारणी सूचकांकों में मैप करता है; प्रत्येक सारणी सूचकांक एक नोड का प्रतिनिधित्व करता है; नोड के मूल, बाईं चाइल्ड शाखा, या दाईं चाइल्ड शाखा का सूचकांक सरल अभिव्यक्ति हैं। शून्य-आधारित सारणी के लिए, रूट नोड को सूचकांक 0 पर संग्रहीत किया जाता है; यदि <code>i</code> , वर्तमान बिन्दु का सूचकांक है
    iParent(i)= floor((i-1) / 2) where floor functions map a real number to thelargest      
   iLeftChild(i)  = 2*i + 1
    iRightChild(i) = 2*i + 2
दूसरे चरण में, एक क्रमबद्ध सारणी बनाया जाता है जिसमें हीप से बार-बार सबसे बड़े तत्व को हटाकर डाला जाता है, और इसे सारणी        में सम्मिलित किया जाता है। प्रत्येक सारणी हटाने के बाद हीप को अद्यतित किया जाता है जिससे हीप गुणधर्म को बनाए रखें।। एक बार जब सभी ऑब्जेक्ट्स को हीप से हटा दिया गया होता है, तो परिणाम एक क्रमबद्ध सारणी होता है।

हीपसॉर्ट को जगह पर ही निष्पादित किया जा सकता है। तथा सारणी को दो भागों में विभाजित किया जा सकता है, जैसे कि क्रमबद्ध सारणी और हीप। हीप को सारणी के रूप में संग्रहीत करने की व्यवस्था यहाँ आरेखित किया गया है। प्रत्येक निष्कर्षण के बाद हीप के अपरिवर्तनीय को संरक्षित किया जाता है, इसलिए एकमात्र लागत निष्कर्षण का होता है।

== कलन विधि ==
हीपसॉर्ट कलन-विधि में, पहले सूची को मैक्स हीप में परिवर्तित करके तैयार किया जाता है। तथा पुनः कलन-विधि में पहले मूल्य को अंतिम मूल्य के साथ प्रतिस्थापित करता है, हीप संचालन में विचार की जाने वाली मानों की सीमा को कम करता है, और नए पहले मूल्य को हीप में उसके स्थान पर स्थानांतरित करता है। यह प्रक्रिया इसलिए बार-बार पुनरावर्ती की जाती है जब तक विचार की जाने वाली मानों की सीमा एक मान की लंबाई में नहीं हो जाती। 

चरण हैं:
# सूची में {{code|buildMaxHeap()}} फलन को कॉल करें। इसे {{code|heapify()}}, भी कहा जाता है, इसे {{tmath|O(n)}} संचालन के माध्यम से सूची से एक हीप बनाता है।.
# सूची के पहले तत्व को अंतिम तत्व के साथ बदलें। सूची की विचार की जाने वाली सीमा को एक के द्वारा कम करें।
# सूची पर {{code|siftDown()}} नए पहले तत्व को हीप  में उसके उपयुक्त सूचकांक में स्थानांतरित करने के लिए सूची पर कार्य करें।
# चरण (2) पर जाएं जब तक कि सूची की मानी गई सीमा एक तत्व न हो।
#{{code|buildMaxHeap()}} संचालन केवल एक बार चलाया जाता है और इसका प्रदर्शन {{math|O(''n'')}}  है। {{code|siftDown()}} फलन {{math|O(log ''n'')}} है और {{math|O(log ''n'')}}, कहा जाता है, और इसे {{mvar|n}} बार कॉल किया जाता है। इसिलिए इस कलन विधि का प्रदर्शन {{math|1=O(''n'' + ''n'' log ''n'') = O(''n'' log ''n'')}}.होता है।

=== [[ छद्मकोड ]] ===

निम्नलिखित [[ छद्मकोड |छद्मकोड]] में कलन विधि को लागू करने का एक सरल विधि दिया गया है। सारणी शून्य पर आधारित होते हैं और स्वैप का उपयोग दो तत्वों का आपस में परिवर्तन करने के लिए किया जाता है। 'नीचे' आगे अर्थात जड़ में से पत्तों की ओर होता है, या निम्न सूचकांक से उच्च सूचकांक की ओर होता है। ध्यान दें कि क्रमबद्धीकरण के समय, सबसे बड़ा तत्व हीप की जड़ पर, <code>a[0]</code> पर होता है, जबकि क्रमबद्धीकरण के अंत में, सबसे बड़ा तत्व<code>a[end]</code> में होता है।

   '''procedure''' heapsort(a, count) '''is'''                                                                                                                         '''input:''' an unordered array ''a'' of length ''count''
  
     ''(Build the heap in array a so that largest value is at the root)''
     heapify(a, count)
 
     ''(The following loop maintains the invariants that a[0:end] is a heap and every element''
      ''beyond end is greater than everything before it (so a[end:count] is in sorted order))''
     end ← count - 1
     '''while''' end > 0 '''do'''
         ''(a[0] is the root and largest value. The swap moves it in front of the sorted elements.)''
         swap(a[end], a[0])
         ''(the heap size is reduced by one)''
         end ← end - 1
         ''(the swap ruined the heap property, so restore it)''
         siftDown(a, 0, end)

सॉर्टिंग रूटीन दो सबरूटिन्स,<code>heapify</code>और  <code>siftDown</code> का उपयोग करता है। पहला सबरूटीन, <code>heapify</code> सामान्य रूप से एक स्थान पर हीप का निर्माण करने के लिए होता है, जबकि दूसरा सबरूटीन, <code>siftDown</code>, <code>heapify</code> को लागू करने के लिए एक सामान्य सबरूटीन होता है।
 ''(Put elements of 'a' in heap order, in-place)''
 '''procedure''' heapify(a, count) '''is'''
     ''(start is assigned the index in 'a' of the last parent node)''
     ''(the last element in a 0-based array is at index count-1; find the parent of that element)''
     start ← iParent(count-1)
     
     '''while''' start ≥ 0 '''do'''
         ''(sift down the node at index 'start' to the proper place such that all nodes below''
          ''the start index are in heap order)''
         siftDown(a, start, count - 1)
         ''(go to the next parent node)''
         start ← start - 1
     ''(after sifting down the root all nodes/elements are in heap order)''
 
 ''(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)''
 '''procedure''' siftDown(a, start, end) '''is'''
     root ← start
 
     '''while''' iLeftChild(root) ≤ end '''do'''    ''(While the root has at least one child)''
         child ← iLeftChild(root)   ''(Left child of root)''
         swap ← root                ''(Keeps track of child to swap with)''
 
         '''if''' a[swap] < a[child] '''then'''
             swap ← child
         ''(If there is a right child and that child is greater)''
         '''if''' child+1 ≤ end '''and''' a[swap] < a[child+1] '''then'''
             swap ← child + 1
         '''if''' swap = root '''then'''
             ''(The root holds the largest element. Since we assume the heaps rooted at the''
              ''children are valid, this means that we are done.)''
 '''else'''                                                                                                     
  '''return''' 
        Swap(a[root], a[swap])                                                                                                                             root ← swap               ''(repeat to continue     sifting down the child now)''            
[[File:Binary heap bottomup vs topdown.svg|thumb|right|सिफ्टडाउन संस्करण और सिफ्टअप संस्करण के बीच समय जटिलता में अंतर।]]heapify  प्रक्रिया को नीचे से ऊपर तक हीप का निर्माण करने के रूप में सोचा जा सकता है, संबंधित हीप संपत्ति स्थापित करने के लिए नीचे की ओर सिफ़्ट करते हुए। एक वैकल्पिक संस्करण जो हीप को ऊपर से नीचे बनाता है और ऊपर सिफ़्ट करता है, समझने में सरल हो सकता है। इस <code>siftUp</code>  संस्करण को रिक्त हीप के साथ आरंभ करके तत्वों को लगातार सम्मिलित करने के रूप में विचार किया जा सकता है, जबकि ऊपर दिए गए <code>siftDown</code> संस्करण में पूरा इनपुट सारणी को एक पूर्ण परंतु "टूटा हुआ" हीप के रूप में देखा जाता है और इसे "पुनर्निर्माण" करता है  यह अंतिम गैर-तुच्छ उपहीप से प्रारंभ होता है। 

हीपीफाई <code>siftDown</code> संस्करण का समय संघटना {{math|''O''(''n'')}} होता है, जबकि नीचे दिए गए <code>siftUp</code> संस्करण का समय संघटना {{math|''O''(''n'' log ''n'')}} होता है, क्योंकि यह प्रत्येक तत्व को एक बार खाली हीप में सम्मिलित करने के समकालीन होता है। इसके परिणामस्वरूप, पहले वाले अवस्थान के तुलनात्मक से प्रतीत होता है,यह स्पष्ट है कि पूर्व अपने लघुगणक-समय स्थानांतरण फलन में बाद वाले के सापेक्ष  में केवल आधी कॉल करता है अर्थात्, उन्हें केवल एक स्थानीय करणात्मक से अलग किया जा सकता है, जो कभी भी अनंतस्पर्शी विश्लेषण को प्रभावित नहीं करता है।

इस विषय में प्राथमिकता प्राप्त करने के लिए, ध्यान दें कि किसी भी एक {{code|siftUp}} कॉल के समय होने वाले स्वैप की संख्या उस नोड की गहराई के साथ बढ़ती है जिस पर कॉल हो रही होती है। मूल बात यह है कि एक हीप  में उथले नोड्स के सापेक्ष  में कई अधिक गहरे नोड होते हैं इसलिए सिफ़्टअप को "बोतम" के निकटस्थ या उसके पास करीबी नोडों पर लगभग रैखिक संख्या में कॉल करने पर उसका पूरा लघुगणकीय कार्यकारी समय हो सकता है। दूसरी ओर, किसी भी एक <code>siftDown</code> कॉल के समय होने वाले स्वैप की संख्या घट जाती है क्योंकि जिस नोड पर कॉल की जाती है उसकी गहराई बढ़ जाती है।

इस प्रकार, जब <code>siftDown</code> <code>heapify</code>  प्रारंभ होती है और नीचे सिफ़्ट को बुलाती है तब सबसे निचले और सबसे अधिक संख्यामय नोड-परतों पर, प्रत्येक सिफ़्टिंग कॉल पर, अधिकतम एक "ऊंचाई" के समान स्वैप की संख्या हो सकती है। दूसरे शब्दों में, लगभग आधी कॉल {{code|siftDown}}की संख्या में अधिकतम केवल एक स्वैप होगी, फिर लगभग चौथाई कॉल में अधिकतम दो स्वैप होंगे, आदि।

स्वयं हीपसॉर्ट कलन विधि की दोनों <code>heapify</code> संस्करणों का उपयोग करके  {{math|''O''(''n'' log ''n'')}} समय संघटना होती है।
      '''procedure''' heapify(a,count) is                                                                                   ''(end is assigned the index of the first (left) child of the root)''
      end := 1
      
      '''while''' end < count
          ''(sift up the node at index end to the proper place such that all nodes above''
           ''the end index are in heap order)''
          siftUp(a, 0, end)
          end := end + 1
      ''(after sifting up the last node all nodes are in heap order)''
  
  '''procedure''' siftUp(a, start, end) '''is'''
      '''input:'''  ''start represents the limit of how far up the heap to sift.''
                    ''end is the node to sift up.''
      child := end 
      '''while''' child > start
          parent := iParent(child)
          '''if''' a[parent] < a[child] '''then''' ''(out of max-heap order)''
              swap(a[parent], a[child])
                 child := parent ''(repeat to continue sifting up the parent now''         '''else'''                                                                                                             
          '''return'''      

ध्यान दें कि <code>siftDown</code> दृष्टिकोण के विपरीत, हर स्वैप के बाद, आपको टूटे हुए हीप को ठीक करने के लिए केवल <code>siftDown</code>प्रक्रिया को कॉल करने की आवश्यकता होती है; परंतु     <code>siftUp</code> प्रक्रिया अकेले टूटे हुए हीप को ठीक नहीं कर सकता। हर बार स्वैप के बाद हीप को <code>heapify</code> प्रक्रिया को कॉल करके बनाना होता है क्योंकि "<code>siftUp</code>" मानता है कि स्वैप होने वाले तत्व का अंतिम स्थान में पहुंचता है, वहीं "<code>siftDown</code>" हीप में नीचे की ओर स्थित वस्तुओं के लिए नियमों को पूरा करने तक निरंतर समायोजन करने की अनुमति देता है। <code>siftUp</code> दृष्टिकोण का उपयोग करने के लिए समायोजित प्यूडोकोड नीचे दिया गया है
     '''procedure''' heapsort(a, count) '''is                                                                      input:''' an unordered array ''a'' of length ''count''
  
     ''(Build the heap in array a so that largest value is at the root)''
     heapify(a, count)
 
     ''(The following loop maintains the invariants that a[0:end] is a heap and every element''
      ''beyond end is greater than everything before it (so a[end:count] is in sorted order))''
     end ← count - 1
     '''while''' end > 0 '''do'''
         ''(a[0] is the root and largest value. The swap moves it in front of the sorted elements.)''
         swap(a[end], a[0])
         ''(rebuild the heap using siftUp after the swap ruins the heap property)''
         heapify(a, end)
         ''(reduce the heap size by one)''
         end ← end - 1
     

==विविधताएं==

=== फ्लोयड का हीप निर्माण ===
सामान्य कलन विधि की सभी व्यावहारिक कार्यान्वयनों में सम्मिलित सबसे महत्वपूर्ण विभिन्नता है फ्लोयड द्वारा संचालित हीप-निर्माण कलन विधि जो {{math|''O''(''n'')}} समय में चलता है और <code>siftDown</code> का उपयोग करता है, <code>siftUp</code> को पूरी तरह से लागू करने की आवश्यकता से बचता है।

फ्लोयड के कलन विधि में, एक छोटे से हीप का प्रारंभ करके पत्तियों को बार-बार जोड़ने की जगह, यह पत्तियों से प्रारंभ करता है, जो अपने-आप में तत्व होते हैं और स्वतः ही छोटे से हीप होते हैं। इसके बाद माता-पिता तत्वों को जोड़ता है। {{mvar|n}}/2 से प्रारंभ करके पिछले काम करते हुए, प्रत्येक आंतरिक बिन्दु को <code>siftDown</code> के द्वारा एक वैध हीप का रूट बनाया जाता है। अंतिम चरण है पहले तत्व को सिफ़्टडाउन करना, इसके बाद पूरे सारणी में हीप गुण का पालन किया जाता है।

फ्लोयड के हीप-निर्माण चरण के दौरान हीपसॉर्ट के सबसे अमान्य स्थितियों में तुलनात्मक संख्या तुलनाएं जानी जाती हैं जो {{math|2''n'' − 2''s''<sub>2</sub>(''n'') − ''e''<sub>2</sub>(''n'')}} के बराबर होती हैं, यहाँ {{math|''s''<sub>2</sub>(''n'')}} के बाइनरी प्रतिष्ठान के 1 बिटों की संख्या है {{mvar|n}} और {{math|''e''<sub>2</sub>(''n'')}} नंबर के पश्चात्तल शून्य बिटों की संख्या होती है।

<ref>{{cite journal
 | last1 = Suchenek | first1 = Marek A.
 | title = Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program
 | doi = 10.3233/FI-2012-751
 | pages = 75–92
 | journal = [[Fundamenta Informaticae]]
 | volume = 120
 | issue = 1
 | year = 2012}}</ref>फ्लोयड के हीप-निर्माण कलन विधि के मानक कार्यान्वयन के कारण डेटा का आकार [[सीपीयू कैश]] से अधिक हो जाने पर बड़ी संख्या में [[कैश मिस]] हो जाता है।{{r|LaMarca99|p=87}} ऊपर वाले स्तर पर आगे बढ़ने से पहले सभी उपहीप्स को एक स्तर पर संयोजित करने के सिवाय, जितनी जल्दी हो सके सबहीप्स को मिलाकर, गहराई-पहले क्रम में विलय करके बड़े डेटा सेट पर बेहतर प्रदर्शन प्राप्त किया जा सकता है।<ref name="Bojesen00">{{cite journal |title=Performance Engineering Case Study: Heap Construction |first1=Jesper |last1=Bojesen |first2=Jyrki |last2=Katajainen |first3=Maz |last3=Spork |journal=ACM Journal of Experimental Algorithmics |date=2000 |volume=5 |pages=15–es |number=15 |doi=10.1145/351827.384257 |citeseerx=10.1.1.35.3248 |s2cid=30995934 |url=http://hjemmesider.diku.dk/~jyrki/Paper/katajain.ps |format=PostScript}} [https://www.semanticscholar.org/paper/Performance-Engineering-Case-Study-Heap-Bojesen-Katajainen/6f4ada5912c1da64e16453d67ec99c970173fb5b Alternate PDF source].</ref><ref>{{cite conference |chapter=In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses |first1=Jingsen |last1=Chen |first2=Stefan |last2=Edelkamp |first3=Amr |last3=Elmasry |first4=Jyrki |last4=Katajainen |title=Mathematical Foundations of Computer Science 2012 |series=Lecture Notes in Computer Science |doi=10.1007/978-3-642-32589-2_25 |conference=37th international conference on Mathematical Foundations of Computer Science |pages=259–270 |location=Bratislava, Slovakia |date=27–31 August 2012 |volume=7464 |isbn=978-3-642-32588-5 |s2cid=1462216 |chapter-url=https://pdfs.semanticscholar.org/9cc6/36d7998d58b3937ba0098e971710ff039612.pdf |archive-url=https://web.archive.org/web/20161229031307/https://pdfs.semanticscholar.org/9cc6/36d7998d58b3937ba0098e971710ff039612.pdf |url-status=dead |archive-date=29 December 2016 }} See particularly Fig. 3.</ref>



=== बॉटम-अप हीप्सॉर्ट ===
बॉटम-अप हीपसॉर्ट एक परिवर्तन है जो आवश्यक तुलनाएं कम करने में अहम भूमिका निभाता है। साधारण हीपसॉर्ट में, सबसे अमान्य     स्थितियों में और औसत में  {{math|2''n'' log<sub>2</sub> ''n'' + ''O''(''n'')}} तुलनाएं की आवश्यकता होती है, जबकि बॉटम-अप परिवर्तन में औसत में {{math|''n'' log<sub>2</sub>''n'' + ''O''(1)}} तुलनाएं की आवश्यकता होती है और सबसे अमान्य स्थितियों में {{math|1.5''n'' log<sub>2</sub>''n'' + ''O''(''n'')}}  तुलनाएं होती हैं।{{r|fleischer}}

यदि तुलनाएं निम्न होती हैं, तो यह अंतर नगण्य होता है, क्योंकि टॉप-डाउन हीपसॉर्ट में मैमोरी से लोड किए गए मानों की तुलना की जाती है। यद्यपि, यदि तुलनाएं फलन कॉल या अन्य जटिल तर्क की आवश्यकता होती है, तो बॉटम-अप हीपसॉर्ट लाभप्रद होता है।

यह सुधार करके पूरा किया गया है <code>siftDown</code> प्रक्रिया। परिवर्तन से रैखिक-समय हीप -निर्माण चरण में कुछ हद तक सुधार होता है,{{r|McDiarmid}} परंतु दूसरे चरण में अधिक महत्वपूर्ण है। सामान्य हीप्सॉर्ट की तरह, दूसरे चरण का प्रत्येक पुनरावृत्ति हीप  के शीर्ष को निकालता है, {{math|''a''[0]}}, और इसके द्वारा छोड़े गए अंतर को भरता है {{math|''a''[''end'']}},पुनः इसके बाद वाले तत्व को हीप के नीचे छानता है। परंतु यह तत्व हीप  के सबसे निचले स्तर से आता है, जिसका अर्थ है कि यह हीप में सबसे छोटे तत्वों में से एक है, इसलिए इसे वापस नीचे ले जाने के लिए छानने वाले को कई कदम उठाने पड़ेंगे।<ref name=MacKay05>{{cite web
 |title=Heapsort, Quicksort, and Entropy
 |first=David J. C. |last=MacKay |author-link=David J. C. MacKay
 |date=December 2005
 |url=https://inference.org.uk/mackay/sorting/sorting.html
 |access-date=2021-02-12
}}</ref> सामान्य हीपसॉर्ट में, सिफ्ट-डाउन का प्रत्येक चरण दो तुलनाएं की आवश्यकता होती है, जिससे तीन तत्वों में से न्यू नोड और उसके दो वंशज का न्यूनतम ढूंढा जा सकता है।

इसके अतिरिक्त बॉटम-अप का उपयोग करके हीपसॉर्ट को पृथक करता है, पता लगाने के लिए लॉग करता है कि ट्री के पत्ते स्तर तक सबसे बड़े नोंड का मार्ग क्या है केवल प्रति स्तर एक तुलना का उपयोग करके दूसरे विधि से कहें तो, यह एक पत्ता खोजता है जिसका यह गुण होता है कि यह और इसके सभी पूर्वज उनके भाईबंधों से अधिक या उसके समान होते हैं। पुनः इस पत्ते से, यह ऊपरी ओर खोज करता है उस मार्ग में सही स्थान के लिए {{math|''a''[''end'']}} को डालने के लिए यही स्थान साधारण हीपसॉर्ट भी खोजता है, और परिवर्तन करने के लिए एक ही संख्या की आवश्यकता होती है, परंतु उस स्थान को ढूंढने के लिए कम तुलनाएं की आवश्यकता होती है।<ref name="fleischer">{{cite journal |last=Fleischer |first=Rudolf |title=बॉटम-अप-हीप्सॉर्ट के सबसे खराब मामले के लिए एक कड़ी निचली सीमा|journal=Algorithmica |volume=11 |issue=2 |date=February 1994 |pages=104–115 |doi=10.1007/bf01182770 |url=http://staff.gutech.edu.om/~rudolf/Paper/buh_algorithmica94.pdf |hdl=11858/00-001M-0000-0014-7B02-C|s2cid=21075180 |hdl-access=free }} Also available as {{cite techreport |last=Fleischer |first=Rudolf |title=बॉटम-अप-हीप्सॉर्ट के सबसे खराब मामले के लिए एक कड़ी निचली सीमा|date=April 1991 |institution=[[Max Planck Institute for Informatics|MPI-INF]] |number=MPI-I-91-104 |url=http://pubman.mpdl.mpg.de/pubman/item/escidoc:1834997:3/component/escidoc:2463941/MPI-I-94-104.pdf}}</ref>क्योंकि यह नीचे तक जाता है और पुनःवापस ऊपर आता है, इसे कुछ लेखकों द्वारा बाउंस के साथ हीपसॉर्ट कहा जाता है।<ref>{{cite book |first1=Bernard |last1=Moret |author-link1=Bernard Moret |first2=Henry D. |last2=Shapiro |title=Algorithms from P to NP Volume 1: Design and Efficiency |chapter=8.6 Heapsort |page=528 |publisher=Benjamin/Cummings |year=1991 |isbn=0-8053-8008-6 |quote=For lack of a better name we call this enhanced program 'heapsort with bounce.{{'-}}}}</ref>
     '''function''' leafSearch(a, i, end) '''is'''                                                                                               j ← i
     '''while''' iRightChild(j) ≤ end '''do'''
         ''(Determine which of j's two children is the greater)''
         '''if''' a[iRightChild(j)] > a[iLeftChild(j)] '''then'''
             j ← iRightChild(j)
         '''else'''
             j ← iLeftChild(j)
     ''(At the last level, there might be only one child)''
     '''if''' iLeftChild(j) ≤ end '''then'''
         j ← iLeftChild(j)
     '''return''' j
<code>leafSearch</code> का रिटर्न मान संशोधित  <code>siftDown</code> रूटीन में उपयोग किया जाता है   
      '''procedure''' siftDown(a, i, end) '''is'''                                                                                                                j ← leafSearch(a, i, end)
     '''while''' a[i] > a[j] '''do'''
         j ← iParent(j)
     x ← a[j]
     a[j] ← a[i]
     '''while''' j > i '''do'''
         swap x, a[iParent(j)]
         j ← iParent(j)
बॉटम-अप हीपसॉर्ट को ≥16000 आकार के सरणियों पर बीटिंग क्विकसॉर्ट के रूप में घोषित किया गया था।{{refn|name=Wegener|{{cite journal |last=Wegener |first=Ingo |author-link=Ingo Wegener |title={{sc|Bottom-Up Heapsort}}, a new variant of {{sc|Heapsort}} beating, on an average, {{sc|Quicksort}} (if {{mvar|n}} is not very small) |journal=Theoretical Computer Science |volume=118 |issue=1 |date=13 September 1993 |pages=81–98 |doi=10.1016/0304-3975(93)90364-y |doi-access=free |url=https://core.ac.uk/download/pdf/82350265.pdf}} Although this is a reprint of work first published in 1990 (at the Mathematical Foundations of Computer Science conference), the technique was published by Carlsson in 1987.<ref name=Carlsson/>}}

2008 में इस कलन-विधि के पुनर्मूल्यांकन से पता चला कि यह पूर्णांक कुंजियों के लिए सामान्य हीपसॉर्ट से अधिक तेज़ नहीं है, संभवतः इसलिए क्योंकि आधुनिक [[शाखा भविष्यवाणी|शाखा]]  पूर्वानुमानित तुलनाओं की लागत को कम कर देती है जिससे बॉटम-अप हीपसॉर्ट बचने का प्रबंधन करता है।<ref name=Melhorn>{{cite book |last1=Mehlhorn |first1=Kurt |author1-link=Kurt Mehlhorn |first2=Peter |last2=Sanders |author2-link=Peter Sanders (computer scientist) |title=Algorithms and Data Structures: The Basic Toolbox |chapter=Priority Queues |publisher=Springer |year=2008 |page=142 |isbn=978-3-540-77977-3 |url=http://people.mpi-inf.mpg.de/~mehlhorn/Toolbox.html |chapter-url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/PriorityQueues.pdf#page=16}}</ref>

एक और परिशोधन चयनित पत्ते के पथ में एक द्विआधारी खोज करता है, और सबसे अमान्य स्थितियो में सॉर्ट करता है {{math|(''n''+1)(log<sub>2</sub>(''n''+1) + log<sub>2</sub> log<sub>2</sub>(''n''+1) + 1.82) + ''O''(log<sub>2</sub>''n'')}} तुलना, तुलनात्मक प्रकार के निकट किसी सूची को क्रमबद्ध करने के लिए आवश्यक तुलनाओं की संख्या सूचना-सैद्धांतिक निचली सीमा {{math|''n'' log<sub>2</sub>''n'' − 1.4427''n''}} से तुलना करता है 

.<ref name="Carlsson">{{cite journal |first=Scante |last=Carlsson |title=तुलनाओं की लगभग इष्टतम संख्या के साथ हीप्सॉर्ट का एक प्रकार|journal=Information Processing Letters |volume=24 |issue=4 |pages=247–250 |date=March 1987 |doi=10.1016/0020-0190(87)90142-6 |s2cid=28135103 |url=https://pdfs.semanticscholar.org/caec/6682ffd13c6367a8c51b566e2420246faca2.pdf |archive-url=https://web.archive.org/web/20161227055904/https://pdfs.semanticscholar.org/caec/6682ffd13c6367a8c51b566e2420246faca2.pdf |url-status=dead |archive-date=2016-12-27 }}</ref>एक वैरिएंट जो प्रति आंतरिक नोड दो अतिरिक्त बिट्स का उपयोग करता है यह जानकारी कैश करने के लिए कि कौन सा वंशज बड़ा है तीन स्थितियो को संग्रहीत करने के लिए दो बिट्स की आवश्यकता होती है: बाएं, दाएं <ref name="McDiarmid">{{Cite journal |title=तेजी से ढेर बना रहे हैं|last1=McDiarmid |first1=C. J. H. |last2=Reed |first2=B. A. |date=September 1989 |journal=Journal of Algorithms |volume=10 |issue=3 |pages=352–365 |doi=10.1016/0196-6774(89)90033-3 |url=http://cgm.cs.mcgill.ca/~breed/2016COMP610/BUILDINGHEAPSFAST.pdf}}</ref> {{math|''n'' log<sub>2</sub>''n'' + 1.1''n''}} तुलना से कम का उपयोग करता है।.<ref>{{cite journal |title=The worst case complexity of McDiarmid and Reed's variant of {{sc|Bottom-Up Heapsort}} is less than ''n''&nbsp;log&nbsp;''n'' + 1.1''n'' |first=Ingo |last=Wegener |author-link=Ingo Wegener |journal=Information and Computation |volume=97 |issue=1 |pages=86–96 |date=March 1992 |doi=10.1016/0890-5401(92)90005-Z |doi-access=free}}</ref>



=== अन्य विविधताएँ ===
*[[ त्रिगुट ढेर |त्रिगुट हीप]] एक त्रिधातु हीप का उपयोग करता है बाइनरी हीप के अतिरिक्त अर्थात प्रत्येक हीप में तीन वंशज होते हैं। {{r|MacKay05}}इसे प्रोग्राम करना अधिक जटिल होता है, परंतु यह स्वैप और तुलना कार्यों को एक स्थिर संख्या को कम करता है। इसका कारण है कि टर्नरी हीप में प्रत्येक सिफ्ट-डाउन चरण में तीन तुलनाएं और एक स्वैप की आवश्यकता होती है, जबकि बाइनरी हीप में दो तुलनाएं और एक स्वैप की आवश्यकता होती है। टर्नरी हीप में दो स्तर द्वारा 32 = 9 तत्वों को कवर किया जाता है, जबकि बाइनरी हीप में तीन स्तरों द्वारा केवल 23 = 8 कवर किए जाते हैं।, क्योंकि अतिरिक्त जटिलता मान्य बचत से योग्य नहीं होती है, और नीचे से ऊपर हीपसॉर्ट दोनों को पीछे छोड़ता है।
*मेमोरी-अनुकूल हीपसॉर्ट{{r|LaMarca99|p=87}}  से यह संदर्भ की स्थानिकता को बढ़ाकर हीपसॉर्ट की सुधार की गई है। इससे तुलनाएं बढ़ जाती हैं, परंतु क्योंकि सभी वंशज क्रमशः मेमोरी में संग्रहीत होते हैं, इसलिए हीप यात्रा के समय एक्सेस किए जाने वाले कैश लाइनों की संख्या को कम करता है, जो एक नेट प्रदर्शन में सुधार करता है।
* जगह से बाहर हीप्सॉर्ट<ref>{{cite conference
 |title=QuickHeapsort, an efficient mix of classical sorting algorithms
 |first1=Domenico |last1=Cantone
 |first2=Gianluca |last2=Concotti
 |conference=4th Italian Conference on Algorithms and Complexity
 |series=Lecture Notes in Computer Science |volume=1767
 |pages=150–162
 |isbn=3-540-67159-5
 |date=1–3 March 2000
 |location=Rome
 |url=https://archive.org/details/springer_10.1007-3-540-46521-9
}}</ref><ref>{{cite journal
 |title=QuickHeapsort, an efficient mix of classical sorting algorithms
 |first1=Domenico |last1=Cantone
 |first2=Gianluca |last2=Concotti
 |journal=Theoretical Computer Science
 |volume=285 |issue=1 |pages=25–42
 |date=August 2002
 |doi=10.1016/S0304-3975(01)00288-2 |doi-access=free
 |zbl=1016.68042
 |url=https://core.ac.uk/download/pdf/81957449.pdf
}}</ref>{{r|MacKay05}} सबसे निम्न स्थिति को समाप्त करके बॉटम-अप हीप्सॉर्ट में सुधार करता है,जहां सभी विषयो को हटा दिया जाता है, न्यूनतम स्थिति को नष्ट किया जाता है {{math|''n'' log<sub>2</sub>''n'' + ''O''(''n'')}} तुलनाएं प्रभाव देता है। जब तुलनाएं अधिकत लिया जाता है, तो असूचित डेटा मान के साथ खाली स्थान को भरने के अतिरिक्त उसे {{math|−∞}} प्रहरी मूल्य, सेंटिनेल मान के साथ भर जाता है, जो कभी   "बाउंस" नहीं करता है। यह प्राथमिकता के रूप में प्रयोग किया जा सकता है इसे इन-प्लेस  क्विकहेप्सॉर्ट कलन विधि में एक आदिम के रूप में उपयोग किया जा सकता है।<ref>{{cite journal
 |title=QuickHeapsort: Modifications and improved analysis
 |first1=Volker |last1=Diekert
 |first2=Armin |last2=Weiß
 |journal= Theory of Computing Systems
 |volume=59 |issue=2 |pages=209–230
 |date=August 2016
 |doi=10.1007/s00224-015-9656-y
<!-- |doi=10.1007/978-3-642-38536-0_3 Conference version, published September 2012-->
 |arxiv=1209.4214
|s2cid=792585 }}</ref> सबसे पहले, आप एक क्विकसॉर्ट-जैसा विभाजन पास करते हैं, परंतु सारणी में विभाजित डेटा के क्रम को उलट देते हैं। मान लीजिए कि छोटा विभाजन धुरी से बड़ा है, जिसे सारणी के अंत में जाना चाहिए, परंतु हमारा उलटा विभाजन चरण से प्रारंभ में रखता है। छोटे विभाजन से एक हीप बनाएं और उस पर जगह से बाहर हीप्सॉर्ट करें, निकाले गए मैक्सिमा को सारणी के अंत से मूल्यों के साथ बदलें। ये धुरी से कम हैं, अर्थात हीप में किसी भी मूल्य से कम हैं, इसलिए इस रूप में कार्य करें। प्रहरी मान.{{math|−∞}} एक बार जब हीपसॉर्ट पूरा हो जाता है तथा विभाजन का क्रम उलट दिया गया है, और सारणी की प्रारंभ  में बड़े विभाजन को उसी तरह से क्रमबद्ध किया जा सकता है।
*[[स्मूथसॉर्ट]] कलन विधि<ref>{{Cite EWD|796a|Smoothsort – an alternative to sorting in situ}}</ref> हीपसॉर्ट का एक विभिन्न रूप है जिसे एड्सगर डाइक्स्ट्रा ने 1981 में विकसित किया था। हीपसॉर्ट की तरह, स्मूथसॉर्ट का ऊपरी सीमा {{math|''O''(''n'' log ''n'')}} होता है। स्मूथसॉर्ट की उपयोगीता यह है कि यदि इनपुट कुछ समय तक पहले से क्रमबद्ध है, तो यह {{math|''O''(''n'')}} के पास आता है, जबकि हीपसॉर्ट का औसत {{math|''O''(''n'' log ''n'')}} होता है इसकी जटिलता के कारण, स्मूथसॉर्ट का उपयोग प्रायः ही कभी किया जाता है।
*लेवकोपोलोस और पीटरसन<ref>{{cite book
 | last1 = Levcopoulos | first1 = Christos
 | last2 = Petersson | first2 = Ola
 | chapter = Heapsort—Adapted for Presorted Files
 | location = London, UK
 | pages = 499–509
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = WADS '89: Proceedings of the Workshop on Algorithms and Data Structures
 | volume = 382 | doi = 10.1007/3-540-51542-9_41
 | year = 1989| isbn = 978-3-540-51542-5
 }} {{Q|56049336}}.</ref> कार्टेशियन ट्री के हीप के आधार पर हीपो की विविधता का वर्णन करें। सबसे पहले, एक कार्टेशियन ट्री इनपुट से बनाया गया है {{math|''O''(''n'')}} समय, और इसकी रूट को 1-तत्व बाइनरी हीप में रखा गया है। पुनः हम बार-बार बाइनरी हीप से न्यूनतम निकालते हैं, ट्री के मूल तत्व को आउटपुट करते हैं, और उसके बाएं और दाएं रूट को बाइनरी हीप में जोड़ते हैं, जो स्वयं कार्टेशियन ट्री हैं।<ref name=":0">{{cite web
 |title=CartesianTreeSort.hh
 |website=Archive of Interesting Code
 |url=http://www.keithschwarz.com/interesting/code/?dir=cartesian-tree-sort
 |first=Keith |last=Schwartz
 |date=27 December 2010 |access-date=2019-03-05
}}</ref> जैसा कि वे दिखाते हैं, यदि इनपुट पहले से ही छोटा किया गया है, तो कार्टेशियन ट्री बहुत असंतुलित होंगे, कुछ नोड्स में बाएं और दाएं रूट होंगे, जिसके परिणामस्वरूप बाइनरी हीप छोटा रहेगा, और कलन विधि को अधिक तेज़ी से सॉर्ट करने की अनुमति मिलेगी उन इनपुट के लिए {{math|''O''(''n'' log ''n'')}} जो पहले से ही लगभग क्रमबद्ध हैं।
* कई प्रकार की विफल हीपसॉर्ट आपत्तिग्रस्त विषय में {{math|''n'' log<sub>2</sub> ''n''+''O''(1)}} तुलनाएं करती हैं, जो संभावित न्यूनतम से नजदीक हैं, प्रति नोड के लिए एक अतिरिक्त बिट के साथ क्षेत्र की आवश्यकता होती है। यद्यपि यह अतिरिक्त बिट कलन- विधि को यथार्थ रूप से इन-प्लेस नहीं बनाता है, यदि उसके लिए स्थान मूल्य में पाया जा सकता है, तो ये कलन- विधि सरल और कुशल होते हैं, 40  परंतु     अगर कुंजी तुलनाएं पर्याप्त सस्ती होती हैं  तो ये अभी भी बाइनरी हीप्स की तुलना में धीमी होती हैं क्योंकि एक स्थिर गुणांक मायने नहीं रखता है।<ref name=":0" />
*कटाजैनेन की "अंतिम हीपसॉर्ट" को कोई अतिरिक्त संग्रहण की आवश्यक नहीं होता है, यह {{math|''n'' log<sub>2</sub> ''n''+''O''(1)}}तुलनाएं करता है, और एक समान क्रमबद्धीकरण आंशिक मूव की संख्या।<ref>{{cite conference |title=अल्टीमेट हीप्सॉर्ट|date=2–3 February 1998 |first=Jyrki |last=Katajainen |conference=Computing: the 4th Australasian Theory Symposium |url=http://hjemmesider.diku.dk/~jyrki/Myris/Kat1998C.html |journal=Australian Computer Science Communications |volume=20 |issue=3 |pages=87–96 |location=Perth }}</ref> यद्यपि,यह और भी अधिक जटिल है और यह उचित नहीं है जब तुलनाएं बहुत महंगी होती हैं ।

== अन्य प्रकार से तुलना ==
हीप्सॉर्ट मुख्य रूप से क्विकसॉर्ट के साथ प्रतिस्पर्धा करता है, जो एक और बहुत ही कुशल सामान्य प्रयोजन इन-प्लेस तुलना-आधारित सॉर्ट कलन विधि है।

हीपसॉर्ट के प्राथमिक लाभ इसके सरल, गैर-[[रिकर्सन (कंप्यूटर विज्ञान)]] कोड, न्यूनतम सहायक भंडारण आवश्यकता और विश्वसनीय रूप से अच्छा प्रदर्शन हैं: इसके सबसे अच्छे और सबसे अमान्य स्थितियों एक-दूसरे के एक छोटे स्थिर कारक के भीतर हैं, और तुलना की संख्या किसी सूची को क्रमबद्ध करना आवश्यक है. जबकि यह इससे बेहतर नहीं कर सकता {{math|''O''(''n'' log ''n'')}} पूर्व-सॉर्ट किए गए इनपुट के लिए, यह क्विकसॉर्ट से प्रभावित नहीं होता है {{math|''O''(''n''<sup>2</sup>)}} सबसे अमान्य स्थिति, या तो। सावधानीपूर्वक कार्यान्वयन से उत्तरार्द्ध से बचा जा सकता है, परंतु यह क्विकॉर्ट को और अधिक जटिल बनाता है, और सबसे लोकप्रिय समाधानों में से एक, इंट्रोसॉर्ट, इस उद्देश्य के लिए हीप्सॉर्ट का उपयोग करता है।

इसका प्राथमिक नुकसान इसके संदर्भ की अमान्य स्थानीयता और इसकी स्वाभाविक रूप से क्रमिक प्रकृति है; अंतर्निहित ट्री तक पहुंच व्यापक रूप से बिखरी हुई है और अधिकतर यादृच्छिक है, और इसे [[समानांतर एल्गोरिदम|समानांतर कलन विधि]] में बदलने का कोई सीधा तरीका नहीं है।इसलिए यह [[ अंतः स्थापित प्रणाली |संगठित प्रणालियों]], [[वास्तविक समय कंप्यूटिंग|वास्तविक समय गणना]] में और कुछ विशेष चयनित इनपुट पर ध्यान देने वाले सिस्टमों में लोकप्रिय हो जाता है<ref>{{cite web
 |work=Data Structures and Algorithms
 |title=Comparing Quick and Heap Sorts
 |type=Lecture notes
 |first=John |last=Morris
 |publisher=University of Western Australia<!--Author and web pages relocated to Auckland since-->
 |year=1998
 |url=https://www.cs.auckland.ac.nz/software/AlgAnim/qsort3.html
 |access-date=2021-02-12
}}</ref>, जैसे लिनक्स कर्नल इसका चयन करना अच्छा विकल्प है<ref>https://github.com/torvalds/linux/blob/master/lib/sort.c Linux kernel source</ref> यह किसी भी एप्लिकेशन के लिए एक अच्छा विकल्प है, जिसे सॉर्ट करते समय किसी रुकावट की आशा नहीं होती है।एक अच्छी तरह से कार्यान्वित क्विकसॉर्ट सामान्यतः  हीपसॉर्ट के सापेक्ष में 2-3 गुना तेज होता है।<ref name="LaMarca99">{{cite journal
 |title=The Influence of Caches on the Performance of Sorting
 |first1=Anthony |last1=LaMarca
 |first2=Richard E. |last2=Ladner |author-link2=Richard E. Ladner
 |journal=Journal of Algorithms |volume=31 |issue=1
 |date=April 1999
 |pages=66–104
 |doi=10.1006/jagm.1998.0985
 |citeseerx=10.1.1.456.3616 <!--10.1.1.155.4400 is the 26-page conference version (Fig. 5c on p. 23) and 10.1.1.84.8929 is a shorter 10-page version (Fig. 2c) -->
 |s2cid=206567217 |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.456.3616&rep=rep1&type=pdf
}} See particularly figure 9c on p. 98.</ref><ref>{{cite web
 |title=Sorting by generating the sorting permutation, and the effect of caching on sorting
 |first=Arne |last=Maus
 |author-link=<!--no:Arne Maus; no en page yet-->
 |date=14 May 2014
 |url=https://www.researchgate.net/publication/228620592
}} See Fig. 1 on p. 6.</ref> यद्यपि क्विकॉर्ट  को कम तुलनाएं की आवश्यकता होती है, यह एक छोटा कारक होता है।का मुख्य फायदा उसकी उत्कृष्ट संदर्भ की स्थानिकता है: विभाजन एक रेखीय  स्कैन है जिसमें अच्छी स्थानिकता होती है, और रिकर्सिव विभाजन में अच्छी कालिक स्थानिकता होती है। अतिरिक्त प्रयास के साथ, क्विकसॉर्ट सामान्यतः अधिकांश शाखामुक्त कोड में लागू किया जा सकता है, और उप-भागों को समानांतर में क्रमबद्ध करने के लिए कई सीपीयू का उपयोग किया जा सकता है। इस प्रकार,क्विकसॉर्ट प्राथमिकता दी जाती है जब अतिरिक्त प्रदर्शन को यथार्थ करता है।

दूसरा प्रमुख {{math|''O''(''n'' log ''n'')}} क्रमबद्धीकरण कलन विधि है, परंतु यह साधारणतः हीपसॉर्ट के साथ सीधे प्रतियोगिता नहीं करता है क्योंकि यह इन-प्लेस नहीं होता है। मर्ज सॉर्ट की {{math|Ω(''n'')}} अतिरिक्त स्थान की आवश्यकता सामान्यतः रोकात्मक होती है, केवल वे स्थितियों में नहीं जहां मर्ज सॉर्ट का स्पष्ट लाभ होता है।
* जब स्थिर क्रमबद्धता की आवश्यकता होती है
* जब (आंशिक रूप से) पूर्व-क्रमबद्ध इनपुट का लाभ उठाना होता है
* युग्मित सूचियाँ को क्रमबद्ध करना (जिसमें मर्ज सॉर्ट को न्यूनतम अतिरिक्त स्थान की आवश्यकता होती है)
* समानांतर क्रमबद्धीकरण;  विलय सॉर्ट क्रमबद्धीकरण से भी बेहतर समानांतर कार्यशील होता है और लगभग रेखांकनीय गति तक प्राप्त कर सकता है
* बाहरी क्रमबद्धीकरण;विलय सॉर्ट में संदर्भ की उत्कृष्ट स्थानिकता होती है।

== उदाहरण ==
हम निम्नलिखित चरणों का पालन करके सूची { 6, 5, 3, 1, 8, 7, 2, 4 } को सबसे छोटे से सबसे बड़े तक क्रमबद्ध करने के लिए हीपसॉर्ट एल्गोरिदम का प्रयोग कर सकते हैं। ध्यान दें, 'हीप निर्माण' चरण के लिए: बड़े नोड छोटे बिन्दु पैरेंट के नीचे रहने के अतिरिक्त पैरेंट के साथ स्वैप किए जाते हैं, और फिर पुनरावृत्ति से यदि आवश्यक हो तो जांचा जाता है कि एक और स्वैप की आवश्यकता है, जिससे हीप द्विआधारी ट्री पर बड़े नंबरों को छोटे नंबरों से ऊपर रखा जा सके।
[[File:Heapsort-example.gif|350px|thumb|right|हीप्सॉर्ट पर एक उदाहरण.]]

=== हीप  बनाएँ ===

{| class="wikitable"
|-
! हीप    !!नया जोड़ा गया तत्व
!तत्वों की अदला-बदली करें
|-
|शून्य
| 6 ||
|-
| 6 || 5 ||
|-
| 6, 5 || 3 ||
|-
| 6, 5, 3 || 1 ||
|-
| 6, 5, 3, 1 || 8 ||
|-
| 6, '''5''', 3, 1, '''8 '''||   || 5, 8
|-
| '''6''', '''8''', 3, 1, 5 ||   || 6, 8
|-
| 8, 6, 3, 1, 5 || 7 || 
|-
| 8, 6, '''3''', 1, 5, '''7''' ||   || 3, 7
|-
| 8, 6, 7, 1, 5, 3 || 2 ||
|-
| 8, 6, 7, 1, 5, 3, 2 || 4 ||
|-
| 8, 6, 7, '''1''', 5, 3, 2, '''4''' ||   || 1, 4
|-
| 8, 6, 7, 4, 5, 3, 2, 1 ||   ||
|}


=== छँटाई ===

{| class="wikitable"
|-
!हीप
!तत्वों की अदला-बदली करें
!तत्व हटाएँ
!क्रमबद्ध सारणी    
!विवरण
|-
| '''8''', 6, 7, 4, 5, 3, 2, '''1''' || 8, 1 ||   ||   ||हीप  से 8 हटाने के लिए 8 और 1 की अदला-बदली करें
|-
| 1, 6, 7, 4, 5, 3, 2, '''8''' ||   || 8 ||   ||हीप  से 8 हटाएं और क्रमबद्ध सारणी     में जोड़ें
|-
| '''1''', 6, '''7''', 4, 5, 3, 2 || 1, 7 ||   || style="text-align: right;" | 8 ||1 और 7 को स्वैप करें क्योंकि वे हीप  में क्रम में नहीं हैं
|-
| 7, 6, '''1''', 4, 5, '''3''', 2 || 1, 3 ||   || style="text-align: right;" | 8 ||1 और 3 को स्वैप करें क्योंकि वे हीप  में क्रम में नहीं हैं
|-
| '''7''', 6, 3, 4, 5, 1, '''2''' || 7, 2 ||   || style="text-align: right;" | 8 ||हीप  से 7 हटाने के लिए 7 और 2 की अदला-बदली करें
|-
| 2, 6, 3, 4, 5, 1, '''7'''       ||      || 7 || style="text-align: right;" | 8 ||हीप  से 7 हटाएं और क्रमबद्ध सारणी     में जोड़ें
|-
| '''2''', '''6''', 3, 4, 5, 1 || 2, 6 ||   || style="text-align: right;" | 7, 8 ||2 और 6 को स्वैप करें क्योंकि वे हीप  में क्रम में नहीं हैं
|-
| 6, '''2''', 3, 4, '''5''', 1 || 2, 5 ||   || style="text-align: right;" | 7, 8 ||2 और 5 को स्वैप करें क्योंकि वे हीप  में क्रम में नहीं हैं
|-
| '''6''', 5, 3, 4, 2, '''1''' || 6, 1 ||   || style="text-align: right;" | 7, 8 ||हीप  से 6 हटाने के लिए 6 और 1 की अदला-बदली करें
|-
| 1, 5, 3, 4, 2, '''6'''          ||   || 6 || style="text-align: right;" | 7, 8 ||हीप  से 6 हटाएं और क्रमबद्ध सारणी     में जोड़ें
|-
| '''1''', '''5''', 3, 4, 2 || 1, 5 ||   || style="text-align: right;" | 6, 7, 8 ||1 और 5 को स्वैप करें क्योंकि वे हीप  में क्रम में नहीं हैं
|-
| 5, '''1''', 3, '''4''', 2 || 1, 4 ||   || style="text-align: right;" | 6, 7, 8 ||1 और 4 को स्वैप करें क्योंकि वे हीप  में क्रम में नहीं हैं
|-
| '''5''', 4, 3, 1, '''2''' || 5, 2 ||   || style="text-align: right;" | 6, 7, 8 ||हीप  से 5 हटाने के लिए 5 और 2 की अदला-बदली करें
|-
| 2, 4, 3, 1, '''5''' ||            || 5 || style="text-align: right;" | 6, 7, 8 ||हीप  से 5 हटाएं और क्रमबद्ध सारणी     में जोड़ें
|-
| '''2''', '''4''', 3, 1 || 2, 4 ||   || style="text-align: right;" | 5, 6, 7, 8 ||2 और 4 को स्वैप करें क्योंकि वे हीप  में क्रम में नहीं हैं
|-
| '''4''', 2, 3, '''1''' || 4, 1 ||   || style="text-align: right;" | 5, 6, 7, 8 ||हीप  से 4 हटाने के लिए 4 और 1 की अदला-बदली करें
|-
| 1, 2, 3, '''4'''          ||   || 4 || style="text-align: right;" | 5, 6, 7, 8 ||हीप  से 4 हटाएं और क्रमबद्ध सारणी     में जोड़ें
|-
| '''1''', 2, '''3''' || 1, 3 ||   || style="text-align: right;" | 4, 5, 6, 7, 8 ||1 और 3 को स्वैप करें क्योंकि वे हीप  में क्रम में नहीं हैं
|-
| '''3''', 2, '''1''' || 3, 1 ||   || style="text-align: right;" | 4, 5, 6, 7, 8 ||हीप  से 3 हटाने के लिए 3 और 1 की अदला-बदली करें
|-
| 1, 2, '''3'''          ||   || 3 || style="text-align: right;" | 4, 5, 6, 7, 8 ||हीप  से 3 हटाएं और क्रमबद्ध सारणी     में जोड़ें
|-
| '''1''', '''2''' || 1, 2 ||   || style="text-align: right;" | 3, 4, 5, 6, 7, 8 ||1 और 2 को स्वैप करें क्योंकि वे हीप  में क्रम में नहीं हैं
|-
| '''2''', '''1''' || 2, 1 ||   || style="text-align: right;" | 3, 4, 5, 6, 7, 8 ||हीप  से 2 हटाने के लिए 2 और 1 की अदला-बदली करें
|-
| 1, '''2''' ||   || 2 || style="text-align: right;" | 3, 4, 5, 6, 7, 8 ||हीप  से 2 हटाएं और क्रमबद्ध सारणी     में जोड़ें
|-
| '''1''' ||   || 1 || style="text-align: right;" | 2, 3, 4, 5, 6, 7, 8 ||हीप  से 1 हटाएं और क्रमबद्ध सारणी     में जोड़ें
|-
|      ||   ||   || style="text-align: right;" | 1, 2, 3, 4, 5, 6, 7, 8 || {{success|Completed}}
|}


== टिप्पणियाँ ==
{{reflist}}


== संदर्भ ==
* {{Cite journal |first=J. W. J. |last=Williams |author-link=J. W. J. Williams |title=Algorithm 232 – Heapsort |year=1964 |journal=[[Communications of the ACM]] |volume=7 |issue=6 |pages=347–348 |doi=10.1145/512274.512284}}
* {{Cite journal |first=Robert W. |last=Floyd |author-link=Robert W. Floyd |title=Algorithm 245 – Treesort 3 |year=1964 |journal=[[Communications of the ACM]] |volume=7 |issue=12 |page=701 |doi= 10.1145/355588.365103 |s2cid=52864987}}
* {{Cite journal |first=Svante |last=Carlsson |author-link=:sv:Svante Carlsson |title=Average-case results on heapsort |year=1987 |journal=[[BIT Numerical Mathematics]] |volume=27 |issue=1 |pages=2–17 |doi= 10.1007/bf01937350 |s2cid=31450060}}
* {{Cite book |first=Donald |last=Knuth |author-link=Donald Knuth |title=[[The Art of Computer Programming]] |volume=3: Sorting and Searching |edition=3rd |publisher=Addison-Wesley |year=1997 |isbn=978-0-201-89685-5 |pages=144–155 |chapter=§5.2.3, Sorting by Selection }}
* {{Cite book |last1=Cormen |first1=Thomas H. |author-link1=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author-link2=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author-link3=Ron Rivest |last4=Stein |first4=Clifford |author-link4=Clifford Stein |year=2001 |title=[[Introduction to Algorithms]] |edition=2nd |publisher=MIT Press and McGraw-Hill |isbn=0-262-03293-7}} Chapters 6 and 7 Respectively: Heapsort and Priority Queues
* [http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF A PDF of Dijkstra's original paper on Smoothsort]
* [http://cis.stvincent.edu/html/tutorials/swd/heaps/heaps.html Heaps and Heapsort Tutorial] by David Carlson, St. Vincent College


== बाहरी संबंध ==
{{wikibooks|Algorithm implementation|Sorting/Heapsort|Heapsort}}
* {{webarchive |url=https://web.archive.org/web/20150306071556/http://www.sorting-algorithms.com/heap-sort |date=6 March 2015 |title=Animated Sorting Algorithms: Heap Sort}} – graphical demonstration
* [https://web.archive.org/web/20130326084250/http://olli.informatik.uni-oldenburg.de/heapsort_SALA/english/start.html Courseware on Heapsort from Univ. Oldenburg] – With text, animations and interactive exercises
* [https://xlinux.nist.gov/dads/HTML/heapSort.html NIST's Dictionary of Algorithms and Data Structures: Heapsort]
* [http://www.codecodex.com/wiki/Heapsort Heapsort implemented in 12 languages]
* [http://www.azillionmonkeys.com/qed/sort.html Sorting revisited] by Paul Hsieh
* [http://employees.oneonta.edu/zhangs/powerPointPlatform/index.php A PowerPoint presentation demonstrating how Heap sort works] that is for educators.
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/11_1_Comparison_Based_Sorti.html#SECTION001413000000000000000 Open Data Structures – Section 11.1.3 – Heap-Sort], [[Pat Morin]]

{{sorting}}

[[Category:CS1]]
[[Category:CS1 errors]]
[[Category:Collapse templates]]
[[Category:Created On 27/06/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Webarchive template wayback links]]
[[Category:Wikipedia metatemplates]]
[[Category:छँटाई एल्गोरिदम]]
[[Category:ढेर (डेटा संरचनाएं)]]
[[Category:तुलना प्रकार]]
[[Category:स्यूडोकोड उदाहरण सहित लेख]]