हीपसॉर्ट: Difference between revisions

हीपसॉर्ट
	हीपसॉर्ट के द्वारा एक यादृच्छिक रूप से विकल्पित मूल्यों के एक एरे को क्रमबद्ध करने की एक रन। एल्गोरिदम के पहले चरण में, एरे के तत्वों को हीप संपत्ति को पूरा करने के लिए पुनः क्रमित किया जाता है। वास्तविक क्रमबद्धीकरण से पहले, चित्रण के लिए हीप ट्री संरचना का संक्षेपण दिखाया जाता है, यह केवल विवरण के लिए है।
Class	Sorting algorithm
Data structure	Array
Worst-case performance
Best-case performance	(distinct keys); or (equal keys)
Average performance
Worst-case space complexity	total auxiliary

Latest revision as of 18:18, 16 July 2023

कंप्यूटर विज्ञान में, हीपसॉर्ट एक तुलना-आधारित क्रमबद्धीकरण कलन विधि है। हीपसॉर्ट को सुधारित सिलेक्शन सॉर्ट के रूप में समझा जा सकता है: चयन सॉर्ट की तरह, हीपसॉर्ट अपने इनपुट को एक क्रमबद्ध और अक्रमबद्ध क्षेत्र में विभाजित करता है और यह अक्रमबद्ध क्षेत्र सतत रूप से क्षेत्र को कम करके बढ़ाता है जिसमें से सबसे बड़ा तत्व निकालकर उसे क्रमबद्ध क्षेत्र में सम्मिलित करता है। इसके विपरीत, हीपसॉर्ट अप्रयुक्त क्षेत्र का रैखिक समय स्कैन के साथ समय व्यर्थ नहीं करता है; बल्कि, हीपसॉर्ट अप्रयुक्त क्षेत्र को हीप डेटा संरचना में बनाए रखकर प्रत्येक स्टेप में सबसे बड़े तत्व को तेजी से खोजने में सहायता करता है।^[1]

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

हीपसॉर्ट का आविष्कार 1964 मेंजे. डब्ल्यू. जे. विलियम्स द्वारा आविष्कृत किया गया था। इससे पहले भी विलियम्स ने हीप को एक उपयुक्त डेटा संरचना के रूप में प्रस्तुत किया था। उसी साल में, रॉबर्ट डब्ल्यू. फ्लॉयड ने एक सुधारित संस्करण प्रकाशित किया था जो किसी सारणी को प्लेस में सॉर्ट कर सकता था, जो उनके पहले ट्रीसॉर्ट कलन विधि के अध्ययन को जारी रखा गया।^[2]

अवलोकन

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

पहले चरण में, डेटा से हीप बनाया जाता है। हीप प्रायः पूर्ण बाइनरी ट्री विन्यास के साथ एक सारणी में रखा जाता है। संपूर्ण बाइनरी ट्री, बाइनरी ट्री संरचना को सारणी सूचकांकों में मैप करता है; प्रत्येक सारणी सूचकांक एक नोड का प्रतिनिधित्व करता है; नोड के मूल, बाईं चाइल्ड शाखा, या दाईं चाइल्ड शाखा का सूचकांक सरल अभिव्यक्ति हैं। शून्य-आधारित सारणी के लिए, रूट नोड को सूचकांक 0 पर संग्रहीत किया जाता है; यदि i , वर्तमान बिन्दु का सूचकांक है

   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

दूसरे चरण में, एक क्रमबद्ध सारणी बनाया जाता है जिसमें हीप से बार-बार सबसे बड़े तत्व को हटाकर डाला जाता है, और इसे सारणी में सम्मिलित किया जाता है। प्रत्येक सारणी हटाने के बाद हीप को अद्यतित किया जाता है जिससे हीप गुणधर्म को बनाए रखें।। एक बार जब सभी ऑब्जेक्ट्स को हीप से हटा दिया गया होता है, तो परिणाम एक क्रमबद्ध सारणी होता है।

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

कलन विधि

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

चरण हैं:

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

छद्मकोड

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

  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)

सॉर्टिंग रूटीन दो सबरूटिन्स,heapifyऔर siftDown का उपयोग करता है। पहला सबरूटीन, heapify सामान्य रूप से एक स्थान पर हीप का निर्माण करने के लिए होता है, जबकि दूसरा सबरूटीन, siftDown, heapify को लागू करने के लिए एक सामान्य सबरूटीन होता है।

(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)

सिफ्टडाउन संस्करण और सिफ्टअप संस्करण के बीच समय जटिलता में अंतर।

heapify प्रक्रिया को नीचे से ऊपर तक हीप का निर्माण करने के रूप में सोचा जा सकता है, संबंधित हीप संपत्ति स्थापित करने के लिए नीचे की ओर सिफ़्ट करते हुए। एक वैकल्पिक संस्करण जो हीप को ऊपर से नीचे बनाता है और ऊपर सिफ़्ट करता है, समझने में सरल हो सकता है। इस siftUp संस्करण को रिक्त हीप के साथ आरंभ करके तत्वों को लगातार सम्मिलित करने के रूप में विचार किया जा सकता है, जबकि ऊपर दिए गए siftDown संस्करण में पूरा इनपुट सारणी को एक पूर्ण परंतु "टूटा हुआ" हीप के रूप में देखा जाता है और इसे "पुनर्निर्माण" करता है यह अंतिम गैर-तुच्छ उपहीप से प्रारंभ होता है।

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

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

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

स्वयं हीपसॉर्ट कलन विधि की दोनों heapify संस्करणों का उपयोग करके $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

ध्यान दें कि siftDown दृष्टिकोण के विपरीत, हर स्वैप के बाद, आपको टूटे हुए हीप को ठीक करने के लिए केवल siftDownप्रक्रिया को कॉल करने की आवश्यकता होती है; परंतु siftUp प्रक्रिया अकेले टूटे हुए हीप को ठीक नहीं कर सकता। हर बार स्वैप के बाद हीप को heapify प्रक्रिया को कॉल करके बनाना होता है क्योंकि "siftUp" मानता है कि स्वैप होने वाले तत्व का अंतिम स्थान में पहुंचता है, वहीं "siftDown" हीप में नीचे की ओर स्थित वस्तुओं के लिए नियमों को पूरा करने तक निरंतर समायोजन करने की अनुमति देता है। siftUp दृष्टिकोण का उपयोग करने के लिए समायोजित प्यूडोकोड नीचे दिया गया है

    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

विविधताएं

फ्लोयड का हीप निर्माण

सामान्य कलन विधि की सभी व्यावहारिक कार्यान्वयनों में सम्मिलित सबसे महत्वपूर्ण विभिन्नता है फ्लोयड द्वारा संचालित हीप-निर्माण कलन विधि जो $O (n)$ समय में चलता है और siftDown का उपयोग करता है, siftUp को पूरी तरह से लागू करने की आवश्यकता से बचता है।

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

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

^[3]फ्लोयड के हीप-निर्माण कलन विधि के मानक कार्यान्वयन के कारण डेटा का आकार सीपीयू कैश से अधिक हो जाने पर बड़ी संख्या में कैश मिस हो जाता है।^[4]^: 87 ऊपर वाले स्तर पर आगे बढ़ने से पहले सभी उपहीप्स को एक स्तर पर संयोजित करने के सिवाय, जितनी जल्दी हो सके सबहीप्स को मिलाकर, गहराई-पहले क्रम में विलय करके बड़े डेटा सेट पर बेहतर प्रदर्शन प्राप्त किया जा सकता है।^[5]^[6]

बॉटम-अप हीप्सॉर्ट

बॉटम-अप हीपसॉर्ट एक परिवर्तन है जो आवश्यक तुलनाएं कम करने में अहम भूमिका निभाता है। साधारण हीपसॉर्ट में, सबसे अमान्य स्थितियों में और औसत में $2 n log 2 n + O (n)$ तुलनाएं की आवश्यकता होती है, जबकि बॉटम-अप परिवर्तन में औसत में $n log 2 n + O (1)$ तुलनाएं की आवश्यकता होती है और सबसे अमान्य स्थितियों में $1.5 n log 2 n + O (n)$ तुलनाएं होती हैं।^[7]

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

यह सुधार करके पूरा किया गया है siftDown प्रक्रिया। परिवर्तन से रैखिक-समय हीप -निर्माण चरण में कुछ हद तक सुधार होता है,^[8] परंतु दूसरे चरण में अधिक महत्वपूर्ण है। सामान्य हीप्सॉर्ट की तरह, दूसरे चरण का प्रत्येक पुनरावृत्ति हीप के शीर्ष को निकालता है, $a [0]$ , और इसके द्वारा छोड़े गए अंतर को भरता है $a [end]$ ,पुनः इसके बाद वाले तत्व को हीप के नीचे छानता है। परंतु यह तत्व हीप के सबसे निचले स्तर से आता है, जिसका अर्थ है कि यह हीप में सबसे छोटे तत्वों में से एक है, इसलिए इसे वापस नीचे ले जाने के लिए छानने वाले को कई कदम उठाने पड़ेंगे।^[9] सामान्य हीपसॉर्ट में, सिफ्ट-डाउन का प्रत्येक चरण दो तुलनाएं की आवश्यकता होती है, जिससे तीन तत्वों में से न्यू नोड और उसके दो वंशज का न्यूनतम ढूंढा जा सकता है।

इसके अतिरिक्त बॉटम-अप का उपयोग करके हीपसॉर्ट को पृथक करता है, पता लगाने के लिए लॉग करता है कि ट्री के पत्ते स्तर तक सबसे बड़े नोंड का मार्ग क्या है केवल प्रति स्तर एक तुलना का उपयोग करके दूसरे विधि से कहें तो, यह एक पत्ता खोजता है जिसका यह गुण होता है कि यह और इसके सभी पूर्वज उनके भाईबंधों से अधिक या उसके समान होते हैं। पुनः इस पत्ते से, यह ऊपरी ओर खोज करता है उस मार्ग में सही स्थान के लिए $a [end]$ को डालने के लिए यही स्थान साधारण हीपसॉर्ट भी खोजता है, और परिवर्तन करने के लिए एक ही संख्या की आवश्यकता होती है, परंतु उस स्थान को ढूंढने के लिए कम तुलनाएं की आवश्यकता होती है।^[7]क्योंकि यह नीचे तक जाता है और पुनःवापस ऊपर आता है, इसे कुछ लेखकों द्वारा बाउंस के साथ हीपसॉर्ट कहा जाता है।^[10]

    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

leafSearch का रिटर्न मान संशोधित siftDown रूटीन में उपयोग किया जाता है

     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 आकार के सरणियों पर बीटिंग क्विकसॉर्ट के रूप में घोषित किया गया था।^[12]

2008 में इस कलन-विधि के पुनर्मूल्यांकन से पता चला कि यह पूर्णांक कुंजियों के लिए सामान्य हीपसॉर्ट से अधिक तेज़ नहीं है, संभवतः इसलिए क्योंकि आधुनिक शाखा पूर्वानुमानित तुलनाओं की लागत को कम कर देती है जिससे बॉटम-अप हीपसॉर्ट बचने का प्रबंधन करता है।^[13]

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

.^[11]एक वैरिएंट जो प्रति आंतरिक नोड दो अतिरिक्त बिट्स का उपयोग करता है यह जानकारी कैश करने के लिए कि कौन सा वंशज बड़ा है तीन स्थितियो को संग्रहीत करने के लिए दो बिट्स की आवश्यकता होती है: बाएं, दाएं ^[8] $n log 2 n + 1.1 n$ तुलना से कम का उपयोग करता है।.^[14]

अन्य विविधताएँ

त्रिगुट हीप एक त्रिधातु हीप का उपयोग करता है बाइनरी हीप के अतिरिक्त अर्थात प्रत्येक हीप में तीन वंशज होते हैं। ^[9]इसे प्रोग्राम करना अधिक जटिल होता है, परंतु यह स्वैप और तुलना कार्यों को एक स्थिर संख्या को कम करता है। इसका कारण है कि टर्नरी हीप में प्रत्येक सिफ्ट-डाउन चरण में तीन तुलनाएं और एक स्वैप की आवश्यकता होती है, जबकि बाइनरी हीप में दो तुलनाएं और एक स्वैप की आवश्यकता होती है। टर्नरी हीप में दो स्तर द्वारा 32 = 9 तत्वों को कवर किया जाता है, जबकि बाइनरी हीप में तीन स्तरों द्वारा केवल 23 = 8 कवर किए जाते हैं।, क्योंकि अतिरिक्त जटिलता मान्य बचत से योग्य नहीं होती है, और नीचे से ऊपर हीपसॉर्ट दोनों को पीछे छोड़ता है।
मेमोरी-अनुकूल हीपसॉर्ट^[4]^: 87 से यह संदर्भ की स्थानिकता को बढ़ाकर हीपसॉर्ट की सुधार की गई है। इससे तुलनाएं बढ़ जाती हैं, परंतु क्योंकि सभी वंशज क्रमशः मेमोरी में संग्रहीत होते हैं, इसलिए हीप यात्रा के समय एक्सेस किए जाने वाले कैश लाइनों की संख्या को कम करता है, जो एक नेट प्रदर्शन में सुधार करता है।
जगह से बाहर हीप्सॉर्ट^[15]^[16]^[9] सबसे निम्न स्थिति को समाप्त करके बॉटम-अप हीप्सॉर्ट में सुधार करता है,जहां सभी विषयो को हटा दिया जाता है, न्यूनतम स्थिति को नष्ट किया जाता है $n log 2 n + O (n)$ तुलनाएं प्रभाव देता है। जब तुलनाएं अधिकत लिया जाता है, तो असूचित डेटा मान के साथ खाली स्थान को भरने के अतिरिक्त उसे $-\infty$ प्रहरी मूल्य, सेंटिनेल मान के साथ भर जाता है, जो कभी "बाउंस" नहीं करता है। यह प्राथमिकता के रूप में प्रयोग किया जा सकता है इसे इन-प्लेस क्विकहेप्सॉर्ट कलन विधि में एक आदिम के रूप में उपयोग किया जा सकता है।^[17] सबसे पहले, आप एक क्विकसॉर्ट-जैसा विभाजन पास करते हैं, परंतु सारणी में विभाजित डेटा के क्रम को उलट देते हैं। मान लीजिए कि छोटा विभाजन धुरी से बड़ा है, जिसे सारणी के अंत में जाना चाहिए, परंतु हमारा उलटा विभाजन चरण से प्रारंभ में रखता है। छोटे विभाजन से एक हीप बनाएं और उस पर जगह से बाहर हीप्सॉर्ट करें, निकाले गए मैक्सिमा को सारणी के अंत से मूल्यों के साथ बदलें। ये धुरी से कम हैं, अर्थात हीप में किसी भी मूल्य से कम हैं, इसलिए इस रूप में कार्य करें। प्रहरी मान. $-\infty$ एक बार जब हीपसॉर्ट पूरा हो जाता है तथा विभाजन का क्रम उलट दिया गया है, और सारणी की प्रारंभ में बड़े विभाजन को उसी तरह से क्रमबद्ध किया जा सकता है।
स्मूथसॉर्ट कलन विधि^[18] हीपसॉर्ट का एक विभिन्न रूप है जिसे एड्सगर डाइक्स्ट्रा ने 1981 में विकसित किया था। हीपसॉर्ट की तरह, स्मूथसॉर्ट का ऊपरी सीमा $O (n log n)$ होता है। स्मूथसॉर्ट की उपयोगीता यह है कि यदि इनपुट कुछ समय तक पहले से क्रमबद्ध है, तो यह $O (n)$ के पास आता है, जबकि हीपसॉर्ट का औसत $O (n log n)$ होता है इसकी जटिलता के कारण, स्मूथसॉर्ट का उपयोग प्रायः ही कभी किया जाता है।
लेवकोपोलोस और पीटरसन^[19] कार्टेशियन ट्री के हीप के आधार पर हीपो की विविधता का वर्णन करें। सबसे पहले, एक कार्टेशियन ट्री इनपुट से बनाया गया है $O (n)$ समय, और इसकी रूट को 1-तत्व बाइनरी हीप में रखा गया है। पुनः हम बार-बार बाइनरी हीप से न्यूनतम निकालते हैं, ट्री के मूल तत्व को आउटपुट करते हैं, और उसके बाएं और दाएं रूट को बाइनरी हीप में जोड़ते हैं, जो स्वयं कार्टेशियन ट्री हैं।^[20] जैसा कि वे दिखाते हैं, यदि इनपुट पहले से ही छोटा किया गया है, तो कार्टेशियन ट्री बहुत असंतुलित होंगे, कुछ नोड्स में बाएं और दाएं रूट होंगे, जिसके परिणामस्वरूप बाइनरी हीप छोटा रहेगा, और कलन विधि को अधिक तेज़ी से सॉर्ट करने की अनुमति मिलेगी उन इनपुट के लिए $O (n log n)$ जो पहले से ही लगभग क्रमबद्ध हैं।
कई प्रकार की विफल हीपसॉर्ट आपत्तिग्रस्त विषय में $n log 2 n + O (1)$ तुलनाएं करती हैं, जो संभावित न्यूनतम से नजदीक हैं, प्रति नोड के लिए एक अतिरिक्त बिट के साथ क्षेत्र की आवश्यकता होती है। यद्यपि यह अतिरिक्त बिट कलन- विधि को यथार्थ रूप से इन-प्लेस नहीं बनाता है, यदि उसके लिए स्थान मूल्य में पाया जा सकता है, तो ये कलन- विधि सरल और कुशल होते हैं, 40 परंतु अगर कुंजी तुलनाएं पर्याप्त सस्ती होती हैं तो ये अभी भी बाइनरी हीप्स की तुलना में धीमी होती हैं क्योंकि एक स्थिर गुणांक मायने नहीं रखता है।^[20]
कटाजैनेन की "अंतिम हीपसॉर्ट" को कोई अतिरिक्त संग्रहण की आवश्यक नहीं होता है, यह $n log 2 n + O (1)$ तुलनाएं करता है, और एक समान क्रमबद्धीकरण आंशिक मूव की संख्या।^[21] यद्यपि,यह और भी अधिक जटिल है और यह उचित नहीं है जब तुलनाएं बहुत महंगी होती हैं ।

अन्य प्रकार से तुलना

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

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

इसका प्राथमिक नुकसान इसके संदर्भ की अमान्य स्थानीयता और इसकी स्वाभाविक रूप से क्रमिक प्रकृति है; अंतर्निहित ट्री तक पहुंच व्यापक रूप से बिखरी हुई है और अधिकतर यादृच्छिक है, और इसे समानांतर कलन विधि में बदलने का कोई सीधा तरीका नहीं है।इसलिए यह संगठित प्रणालियों, वास्तविक समय गणना में और कुछ विशेष चयनित इनपुट पर ध्यान देने वाले सिस्टमों में लोकप्रिय हो जाता है^[22], जैसे लिनक्स कर्नल इसका चयन करना अच्छा विकल्प है^[23] यह किसी भी एप्लिकेशन के लिए एक अच्छा विकल्प है, जिसे सॉर्ट करते समय किसी रुकावट की आशा नहीं होती है।एक अच्छी तरह से कार्यान्वित क्विकसॉर्ट सामान्यतः हीपसॉर्ट के सापेक्ष में 2-3 गुना तेज होता है।^[4]^[24] यद्यपि क्विकॉर्ट को कम तुलनाएं की आवश्यकता होती है, यह एक छोटा कारक होता है।का मुख्य फायदा उसकी उत्कृष्ट संदर्भ की स्थानिकता है: विभाजन एक रेखीय स्कैन है जिसमें अच्छी स्थानिकता होती है, और रिकर्सिव विभाजन में अच्छी कालिक स्थानिकता होती है। अतिरिक्त प्रयास के साथ, क्विकसॉर्ट सामान्यतः अधिकांश शाखामुक्त कोड में लागू किया जा सकता है, और उप-भागों को समानांतर में क्रमबद्ध करने के लिए कई सीपीयू का उपयोग किया जा सकता है। इस प्रकार,क्विकसॉर्ट प्राथमिकता दी जाती है जब अतिरिक्त प्रदर्शन को यथार्थ करता है।

दूसरा प्रमुख $O (n log n)$ क्रमबद्धीकरण कलन विधि है, परंतु यह साधारणतः हीपसॉर्ट के साथ सीधे प्रतियोगिता नहीं करता है क्योंकि यह इन-प्लेस नहीं होता है। मर्ज सॉर्ट की $Ω(n)$ अतिरिक्त स्थान की आवश्यकता सामान्यतः रोकात्मक होती है, केवल वे स्थितियों में नहीं जहां मर्ज सॉर्ट का स्पष्ट लाभ होता है।

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

उदाहरण

हम निम्नलिखित चरणों का पालन करके सूची { 6, 5, 3, 1, 8, 7, 2, 4 } को सबसे छोटे से सबसे बड़े तक क्रमबद्ध करने के लिए हीपसॉर्ट एल्गोरिदम का प्रयोग कर सकते हैं। ध्यान दें, 'हीप निर्माण' चरण के लिए: बड़े नोड छोटे बिन्दु पैरेंट के नीचे रहने के अतिरिक्त पैरेंट के साथ स्वैप किए जाते हैं, और फिर पुनरावृत्ति से यदि आवश्यक हो तो जांचा जाता है कि एक और स्वैप की आवश्यकता है, जिससे हीप द्विआधारी ट्री पर बड़े नंबरों को छोटे नंबरों से ऊपर रखा जा सके।

हीप्सॉर्ट पर एक उदाहरण.

हीप बनाएँ

हीप	नया जोड़ा गया तत्व	तत्वों की अदला-बदली करें
शून्य	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

छँटाई

हीप	तत्वों की अदला-बदली करें	तत्व हटाएँ	क्रमबद्ध सारणी	विवरण
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		8	1 और 7 को स्वैप करें क्योंकि वे हीप में क्रम में नहीं हैं
7, 6, 1, 4, 5, 3, 2	1, 3		8	1 और 3 को स्वैप करें क्योंकि वे हीप में क्रम में नहीं हैं
7, 6, 3, 4, 5, 1, 2	7, 2		8	हीप से 7 हटाने के लिए 7 और 2 की अदला-बदली करें
2, 6, 3, 4, 5, 1, 7		7	8	हीप से 7 हटाएं और क्रमबद्ध सारणी में जोड़ें
2, 6, 3, 4, 5, 1	2, 6		7, 8	2 और 6 को स्वैप करें क्योंकि वे हीप में क्रम में नहीं हैं
6, 2, 3, 4, 5, 1	2, 5		7, 8	2 और 5 को स्वैप करें क्योंकि वे हीप में क्रम में नहीं हैं
6, 5, 3, 4, 2, 1	6, 1		7, 8	हीप से 6 हटाने के लिए 6 और 1 की अदला-बदली करें
1, 5, 3, 4, 2, 6		6	7, 8	हीप से 6 हटाएं और क्रमबद्ध सारणी में जोड़ें
1, 5, 3, 4, 2	1, 5		6, 7, 8	1 और 5 को स्वैप करें क्योंकि वे हीप में क्रम में नहीं हैं
5, 1, 3, 4, 2	1, 4		6, 7, 8	1 और 4 को स्वैप करें क्योंकि वे हीप में क्रम में नहीं हैं
5, 4, 3, 1, 2	5, 2		6, 7, 8	हीप से 5 हटाने के लिए 5 और 2 की अदला-बदली करें
2, 4, 3, 1, 5		5	6, 7, 8	हीप से 5 हटाएं और क्रमबद्ध सारणी में जोड़ें
2, 4, 3, 1	2, 4		5, 6, 7, 8	2 और 4 को स्वैप करें क्योंकि वे हीप में क्रम में नहीं हैं
4, 2, 3, 1	4, 1		5, 6, 7, 8	हीप से 4 हटाने के लिए 4 और 1 की अदला-बदली करें
1, 2, 3, 4		4	5, 6, 7, 8	हीप से 4 हटाएं और क्रमबद्ध सारणी में जोड़ें
1, 2, 3	1, 3		4, 5, 6, 7, 8	1 और 3 को स्वैप करें क्योंकि वे हीप में क्रम में नहीं हैं
3, 2, 1	3, 1		4, 5, 6, 7, 8	हीप से 3 हटाने के लिए 3 और 1 की अदला-बदली करें
1, 2, 3		3	4, 5, 6, 7, 8	हीप से 3 हटाएं और क्रमबद्ध सारणी में जोड़ें
1, 2	1, 2		3, 4, 5, 6, 7, 8	1 और 2 को स्वैप करें क्योंकि वे हीप में क्रम में नहीं हैं
2, 1	2, 1		3, 4, 5, 6, 7, 8	हीप से 2 हटाने के लिए 2 और 1 की अदला-बदली करें
1, 2		2	3, 4, 5, 6, 7, 8	हीप से 2 हटाएं और क्रमबद्ध सारणी में जोड़ें
1		1	2, 3, 4, 5, 6, 7, 8	हीप से 1 हटाएं और क्रमबद्ध सारणी में जोड़ें
			1, 2, 3, 4, 5, 6, 7, 8	Completed

↑ Skiena, Steven (2008). "Searching and Sorting". एल्गोरिथम डिज़ाइन मैनुअल. Springer. p. 109. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8. [H]eapsort is nothing but an implementation of selection sort using the right data structure.
↑ Brass, Peter (2008). उन्नत डेटा संरचनाएँ. Cambridge University Press. p. 209. ISBN 978-0-521-88037-4.
↑ Suchenek, Marek A. (2012). "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program". Fundamenta Informaticae. 120 (1): 75–92. doi:10.3233/FI-2012-751.
↑ ^4.0 ^4.1 ^4.2 LaMarca, Anthony; Ladner, Richard E. (April 1999). "The Influence of Caches on the Performance of Sorting". Journal of Algorithms. 31 (1): 66–104. CiteSeerX 10.1.1.456.3616. doi:10.1006/jagm.1998.0985. S2CID 206567217. See particularly figure 9c on p. 98.
↑ Bojesen, Jesper; Katajainen, Jyrki; Spork, Maz (2000). "Performance Engineering Case Study: Heap Construction" (PostScript). ACM Journal of Experimental Algorithmics. 5 (15): 15–es. CiteSeerX 10.1.1.35.3248. doi:10.1145/351827.384257. S2CID 30995934. Alternate PDF source.
↑ Chen, Jingsen; Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (27–31 August 2012). "In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses" (PDF). Mathematical Foundations of Computer Science 2012. 37th international conference on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science. Vol. 7464. Bratislava, Slovakia. pp. 259–270. doi:10.1007/978-3-642-32589-2_25. ISBN 978-3-642-32588-5. S2CID 1462216. Archived from the original (PDF) on 29 December 2016. See particularly Fig. 3.
↑ ^7.0 ^7.1 Fleischer, Rudolf (February 1994). "बॉटम-अप-हीप्सॉर्ट के सबसे खराब मामले के लिए एक कड़ी निचली सीमा" (PDF). Algorithmica. 11 (2): 104–115. doi:10.1007/bf01182770. hdl:11858/00-001M-0000-0014-7B02-C. S2CID 21075180. Also available as Fleischer, Rudolf (April 1991). बॉटम-अप-हीप्सॉर्ट के सबसे खराब मामले के लिए एक कड़ी निचली सीमा (PDF) (Technical report). MPI-INF. MPI-I-91-104.
↑ ^8.0 ^8.1 McDiarmid, C. J. H.; Reed, B. A. (September 1989). "तेजी से ढेर बना रहे हैं" (PDF). Journal of Algorithms. 10 (3): 352–365. doi:10.1016/0196-6774(89)90033-3.
↑ ^9.0 ^9.1 ^9.2 MacKay, David J. C. (December 2005). "Heapsort, Quicksort, and Entropy". Retrieved 2021-02-12.
↑ Moret, Bernard; Shapiro, Henry D. (1991). "8.6 Heapsort". Algorithms from P to NP Volume 1: Design and Efficiency. Benjamin/Cummings. p. 528. ISBN 0-8053-8008-6. For lack of a better name we call this enhanced program 'heapsort with bounce.'
↑ ^11.0 ^11.1 Carlsson, Scante (March 1987). "तुलनाओं की लगभग इष्टतम संख्या के साथ हीप्सॉर्ट का एक प्रकार" (PDF). Information Processing Letters. 24 (4): 247–250. doi:10.1016/0020-0190(87)90142-6. S2CID 28135103. Archived from the original (PDF) on 2016-12-27.
↑ Wegener, Ingo (13 September 1993). "BOTTOM-UP HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if $n$ [[Category: Templates Vigyan Ready]] is not very small)" (PDF). Theoretical Computer Science. 118 (1): 81–98. doi:10.1016/0304-3975(93)90364-y. {{cite journal}}: URL–wikilink conflict (help) 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.^[11]
↑ Mehlhorn, Kurt; Sanders, Peter (2008). "Priority Queues" (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer. p. 142. ISBN 978-3-540-77977-3.
↑ Wegener, Ingo (March 1992). "The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than n log n + 1.1n". Information and Computation. 97 (1): 86–96. doi:10.1016/0890-5401(92)90005-Z.
↑ Cantone, Domenico; Concotti, Gianluca (1–3 March 2000). QuickHeapsort, an efficient mix of classical sorting algorithms. 4th Italian Conference on Algorithms and Complexity. Lecture Notes in Computer Science. Vol. 1767. Rome. pp. 150–162. ISBN 3-540-67159-5.
↑ Cantone, Domenico; Concotti, Gianluca (August 2002). "QuickHeapsort, an efficient mix of classical sorting algorithms" (PDF). Theoretical Computer Science. 285 (1): 25–42. doi:10.1016/S0304-3975(01)00288-2. Zbl 1016.68042.
↑ Diekert, Volker; Weiß, Armin (August 2016). "QuickHeapsort: Modifications and improved analysis". Theory of Computing Systems. 59 (2): 209–230. arXiv:1209.4214. doi:10.1007/s00224-015-9656-y. S2CID 792585.
↑ Dijkstra, Edsger W. Smoothsort – an alternative to sorting in situ (EWD-796a) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription)
↑ Levcopoulos, Christos; Petersson, Ola (1989). "Heapsort—Adapted for Presorted Files". WADS '89: Proceedings of the Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science. Vol. 382. London, UK: Springer-Verlag. pp. 499–509. doi:10.1007/3-540-51542-9_41. ISBN 978-3-540-51542-5. Script error: The module returned a nil value. It is supposed to return an export table. (Q56049336).
↑ ^20.0 ^20.1 Schwartz, Keith (27 December 2010). "CartesianTreeSort.hh". Archive of Interesting Code. Retrieved 2019-03-05.
↑ Katajainen, Jyrki (2–3 February 1998). अल्टीमेट हीप्सॉर्ट. Computing: the 4th Australasian Theory Symposium. Australian Computer Science Communications. Vol. 20, no. 3. Perth. pp. 87–96.
↑ Morris, John (1998). "Comparing Quick and Heap Sorts". Data Structures and Algorithms (Lecture notes). University of Western Australia. Retrieved 2021-02-12.
↑ https://github.com/torvalds/linux/blob/master/lib/sort.c Linux kernel source
↑ Maus, Arne (14 May 2014). "Sorting by generating the sorting permutation, and the effect of caching on sorting". See Fig. 1 on p. 6.

संदर्भ

Williams, J. W. J. (1964). "Algorithm 232 – Heapsort". Communications of the ACM. 7 (6): 347–348. doi:10.1145/512274.512284.
Floyd, Robert W. (1964). "Algorithm 245 – Treesort 3". Communications of the ACM. 7 (12): 701. doi:10.1145/355588.365103. S2CID 52864987.
Carlsson, Svante [in svenska] (1987). "Average-case results on heapsort". BIT Numerical Mathematics. 27 (1): 2–17. doi:10.1007/bf01937350. S2CID 31450060.
Knuth, Donald (1997). "§5.2.3, Sorting by Selection". The Art of Computer Programming. Vol. 3: Sorting and Searching (3rd ed.). Addison-Wesley. pp. 144–155. ISBN 978-0-201-89685-5.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. Chapters 6 and 7 Respectively: Heapsort and Priority Queues
A PDF of Dijkstra's original paper on Smoothsort
Heaps and Heapsort Tutorial by David Carlson, St. Vincent College

बाहरी संबंध

Animated Sorting Algorithms: Heap Sort at the Wayback Machine (archived 6 March 2015) – graphical demonstration
Courseware on Heapsort from Univ. Oldenburg – With text, animations and interactive exercises
NIST's Dictionary of Algorithms and Data Structures: Heapsort
Heapsort implemented in 12 languages
Sorting revisited by Paul Hsieh
A PowerPoint presentation demonstrating how Heap sort works that is for educators.
Open Data Structures – Section 11.1.3 – Heap-Sort, Pat Morin

[1] Skiena, Steven (2008). "Searching and Sorting". एल्गोरिथम डिज़ाइन मैनुअल. Springer. p. 109. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8. [H]eapsort is nothing but an implementation of selection sort using the right data structure.

[brass-2] Brass, Peter (2008). उन्नत डेटा संरचनाएँ. Cambridge University Press. p. 209. ISBN 978-0-521-88037-4.

[3] Suchenek, Marek A. (2012). "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program". Fundamenta Informaticae. 120 (1): 75–92. doi:10.3233/FI-2012-751.

[LaMarca99-4] 4.0 ^4.1 ^4.2 LaMarca, Anthony; Ladner, Richard E. (April 1999). "The Influence of Caches on the Performance of Sorting". Journal of Algorithms. 31 (1): 66–104. CiteSeerX 10.1.1.456.3616. doi:10.1006/jagm.1998.0985. S2CID 206567217. See particularly figure 9c on p. 98.

[Bojesen00-5] Bojesen, Jesper; Katajainen, Jyrki; Spork, Maz (2000). "Performance Engineering Case Study: Heap Construction" (PostScript). ACM Journal of Experimental Algorithmics. 5 (15): 15–es. CiteSeerX 10.1.1.35.3248. doi:10.1145/351827.384257. S2CID 30995934. Alternate PDF source.

[6] Chen, Jingsen; Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (27–31 August 2012). "In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses" (PDF). Mathematical Foundations of Computer Science 2012. 37th international conference on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science. Vol. 7464. Bratislava, Slovakia. pp. 259–270. doi:10.1007/978-3-642-32589-2_25. ISBN 978-3-642-32588-5. S2CID 1462216. Archived from the original (PDF) on 29 December 2016. See particularly Fig. 3.

[fleischer-7] 7.0 ^7.1 Fleischer, Rudolf (February 1994). "बॉटम-अप-हीप्सॉर्ट के सबसे खराब मामले के लिए एक कड़ी निचली सीमा" (PDF). Algorithmica. 11 (2): 104–115. doi:10.1007/bf01182770. hdl:11858/00-001M-0000-0014-7B02-C. S2CID 21075180. Also available as Fleischer, Rudolf (April 1991). बॉटम-अप-हीप्सॉर्ट के सबसे खराब मामले के लिए एक कड़ी निचली सीमा (PDF) (Technical report). MPI-INF. MPI-I-91-104.

[McDiarmid-8] 8.0 ^8.1 McDiarmid, C. J. H.; Reed, B. A. (September 1989). "तेजी से ढेर बना रहे हैं" (PDF). Journal of Algorithms. 10 (3): 352–365. doi:10.1016/0196-6774(89)90033-3.

[MacKay05-9] 9.0 ^9.1 ^9.2 MacKay, David J. C. (December 2005). "Heapsort, Quicksort, and Entropy". Retrieved 2021-02-12.

[10] Moret, Bernard; Shapiro, Henry D. (1991). "8.6 Heapsort". Algorithms from P to NP Volume 1: Design and Efficiency. Benjamin/Cummings. p. 528. ISBN 0-8053-8008-6. For lack of a better name we call this enhanced program 'heapsort with bounce.'

[Carlsson-11] 11.0 ^11.1 Carlsson, Scante (March 1987). "तुलनाओं की लगभग इष्टतम संख्या के साथ हीप्सॉर्ट का एक प्रकार" (PDF). Information Processing Letters. 24 (4): 247–250. doi:10.1016/0020-0190(87)90142-6. S2CID 28135103. Archived from the original (PDF) on 2016-12-27.

[Wegener-12] Wegener, Ingo (13 September 1993). "BOTTOM-UP HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if $n$ [[Category: Templates Vigyan Ready]] is not very small)" (PDF). Theoretical Computer Science. 118 (1): 81–98. doi:10.1016/0304-3975(93)90364-y. {{cite journal}}: URL–wikilink conflict (help) 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.^[11]

[Melhorn-13] Mehlhorn, Kurt; Sanders, Peter (2008). "Priority Queues" (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer. p. 142. ISBN 978-3-540-77977-3.

[14] Wegener, Ingo (March 1992). "The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than n log n + 1.1n". Information and Computation. 97 (1): 86–96. doi:10.1016/0890-5401(92)90005-Z.

[15] Cantone, Domenico; Concotti, Gianluca (1–3 March 2000). QuickHeapsort, an efficient mix of classical sorting algorithms. 4th Italian Conference on Algorithms and Complexity. Lecture Notes in Computer Science. Vol. 1767. Rome. pp. 150–162. ISBN 3-540-67159-5.

[16] Cantone, Domenico; Concotti, Gianluca (August 2002). "QuickHeapsort, an efficient mix of classical sorting algorithms" (PDF). Theoretical Computer Science. 285 (1): 25–42. doi:10.1016/S0304-3975(01)00288-2. Zbl 1016.68042.

[17] Diekert, Volker; Weiß, Armin (August 2016). "QuickHeapsort: Modifications and improved analysis". Theory of Computing Systems. 59 (2): 209–230. arXiv:1209.4214. doi:10.1007/s00224-015-9656-y. S2CID 792585.

[18] Dijkstra, Edsger W. Smoothsort – an alternative to sorting in situ (EWD-796a) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription)

[19] Levcopoulos, Christos; Petersson, Ola (1989). "Heapsort—Adapted for Presorted Files". WADS '89: Proceedings of the Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science. Vol. 382. London, UK: Springer-Verlag. pp. 499–509. doi:10.1007/3-540-51542-9_41. ISBN 978-3-540-51542-5. Script error: The module returned a nil value. It is supposed to return an export table. (Q56049336).

[:0-20] 20.0 ^20.1 Schwartz, Keith (27 December 2010). "CartesianTreeSort.hh". Archive of Interesting Code. Retrieved 2019-03-05.

[21] Katajainen, Jyrki (2–3 February 1998). अल्टीमेट हीप्सॉर्ट. Computing: the 4th Australasian Theory Symposium. Australian Computer Science Communications. Vol. 20, no. 3. Perth. pp. 87–96.

[22] Morris, John (1998). "Comparing Quick and Heap Sorts". Data Structures and Algorithms (Lecture notes). University of Western Australia. Retrieved 2021-02-12.

[23] ttps://github.com/torvalds/linux/blob/master/lib/sort.c Linux kernel source

[24] Maus, Arne (14 May 2014). "Sorting by generating the sorting permutation, and the effect of caching on sorting". See Fig. 1 on p. 6.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[12]

[13]

[11]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort Slowsort Stooge sort Bogosort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort

Anonymous

Search

हीपसॉर्ट: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 18:18, 16 July 2023

Contents

अवलोकन

कलन विधि

छद्मकोड

विविधताएं

फ्लोयड का हीप निर्माण

बॉटम-अप हीप्सॉर्ट

अन्य विविधताएँ

अन्य प्रकार से तुलना

उदाहरण

हीप बनाएँ

छँटाई

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 3: / Line 3: @@
 {{Infobox Algorithm|class=[[Sorting algorithm]]
 |image=[[File:Sorting heapsort anim.gif]]
-|caption=A run of heapsort sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the [[Heap (data structure)|heap property]]. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration.
+|caption=हीपसॉर्ट के द्वारा एक यादृच्छिक रूप से विकल्पित मूल्यों के एक एरे को क्रमबद्ध करने की एक रन। एल्गोरिदम के पहले चरण में, एरे के तत्वों को हीप संपत्ति को पूरा करने के लिए पुनः क्रमित किया जाता है। वास्तविक क्रमबद्धीकरण से पहले, चित्रण के लिए हीप ट्री संरचना का संक्षेपण दिखाया जाता है, यह केवल विवरण के लिए है।
 |data=[[Array data structure|Array]]
 |time=<math>O(n\log n)</math>
@@ Line 14: / Line 14: @@
 यद्यपि बहुत से यंत्रों पर अच्छी तरह से लागू किए गए क्विकसॉर्ट से कुछ धीमा होता है, हीपसॉर्ट का लाभ एक अधिक सकारात्मक वर्स्ट-केस {{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>
+हीपसॉर्ट का आविष्कार 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>
 == अवलोकन ==
-हीपसॉर्ट एल्गोरिदम को दो भागों में विभाजित किया जा सकता है।
+हीपसॉर्ट कलन-विधि को दो भागों में विभाजित किया जा सकता है।
-पहले चरण में, डेटा से एक हीप (डेटा संरचना) बनाया जाता है (देखें)। {{section link|Binary heap#Building a heap}}). ढेर को अक्सर एक पूर्ण बाइनरी ट्री #बाइनरी ट्री के प्रकार के लेआउट के साथ एक सरणी में रखा जाता है। संपूर्ण बाइनरी ट्री, बाइनरी ट्री संरचना को सरणी सूचकांकों में मैप करता है; प्रत्येक सरणी सूचकांक एक नोड का प्रतिनिधित्व करता है; नोड के मूल, बाईं चाइल्ड शाखा, या दाईं चाइल्ड शाखा का सूचकांक सरल अभिव्यक्ति हैं। शून्य-आधारित सरणी के लिए, रूट नोड को इंडेक्स 0 पर संग्रहीत किया जाता है; अगर <code>i</code> तो, वर्तमान नोड का सूचकांक है
+पहले चरण में, डेटा से हीप बनाया जाता है। हीप प्रायः पूर्ण बाइनरी ट्री विन्यास के साथ एक सारणी में रखा जाता है। संपूर्ण बाइनरी ट्री, बाइनरी ट्री संरचना को सारणी सूचकांकों में मैप करता है; प्रत्येक सारणी सूचकांक एक नोड का प्रतिनिधित्व करता है; नोड के मूल, बाईं चाइल्ड शाखा, या दाईं चाइल्ड शाखा का सूचकांक सरल अभिव्यक्ति हैं। शून्य-आधारित सारणी के लिए, रूट नोड को सूचकांक 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|buildMaxHeap()}} फलन को कॉल करें। इसे {{code|heapify()}}, भी कहा जाता है, इसे {{tmath|O(n)}} संचालन के माध्यम से सूची से एक हीप बनाता है।.
-# सूची के पहले तत्व को अंतिम तत्व से बदलें। सूची की सुविचारित सीमा को एक से कम करें।
+# सूची के पहले तत्व को अंतिम तत्व के साथ बदलें। सूची की विचार की जाने वाली सीमा को एक के द्वारा कम करें।
-# बुलाएं {{code|siftDown()}} नए पहले तत्व को ढेर में उसके उपयुक्त सूचकांक में स्थानांतरित करने के लिए सूची पर कार्य करें।
+# सूची पर {{code|siftDown()}} नए पहले तत्व को हीप  में उसके उपयुक्त सूचकांक में स्थानांतरित करने के लिए सूची पर कार्य करें।
-# चरण (2) पर जाएं जब तक कि सूची की मानी गई सीमा एक तत्व न हो। वह {{code|buildMaxHeap()}} ऑपरेशन एक बार चलाया जाता है, और है {{math|O(''n'')}} प्रदर्शन में. वह {{code|siftDown()}} फ़ंक्शन है {{math|O(log ''n'')}}, और कहा जाता है {{mvar|n}} बार. इसलिए, इस एल्गोरिदम का प्रदर्शन है {{math|1=O(''n'' + ''n'' log ''n'') = O(''n'' log ''n'')}}.
+# चरण (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>swap</code> सरणी के दो तत्वों का आदान-प्रदान करने के लिए उपयोग किया जाता है। 'नीचे' गति का अर्थ है जड़ से पत्तियों की ओर, या निम्न सूचकांक से उच्चतर की ओर। ध्यान दें कि सॉर्ट के दौरान, सबसे बड़ा तत्व ढेर के मूल में होता है <code>a[0]</code>, जबकि सॉर्ट के अंत में, सबसे बड़ा तत्व अंदर है <code>a[end]</code>.
+निम्नलिखित [[ छद्मकोड |छद्मकोड]] में कलन विधि को लागू करने का एक सरल विधि दिया गया है। सारणी शून्य पर आधारित होते हैं और स्वैप का उपयोग दो तत्वों का आपस में परिवर्तन करने के लिए किया जाता है। 'नीचे' आगे अर्थात जड़ में से पत्तों की ओर होता है, या निम्न सूचकांक से उच्च सूचकांक की ओर होता है। ध्यान दें कि क्रमबद्धीकरण के समय, सबसे बड़ा तत्व हीप की जड़ पर, <code>a[0]</code> पर होता है, जबकि क्रमबद्धीकरण के अंत में, सबसे बड़ा तत्व<code>a[end]</code> में होता है।
     '''procedure''' heapsort(a, count) '''is'''                                                                                                                         '''input:''' an unordered array ''a'' of length ''count''
@@ Line 58: / Line 59: @@
           siftDown(a, 0, end)
+सॉर्टिंग रूटीन दो सबरूटिन्स,<code>heapify</code>और  <code>siftDown</code> का उपयोग करता है। पहला सबरूटीन, <code>heapify</code> सामान्य रूप से एक स्थान पर हीप का निर्माण करने के लिए होता है, जबकि दूसरा सबरूटीन, <code>siftDown</code>, <code>heapify</code> को लागू करने के लिए एक सामान्य सबरूटीन होता है।
-सॉर्टिंग रूटीन दो सबरूटीन्स का उपयोग करता है, <code>heapify</code> और <code>siftDown</code>. पहला सामान्य इन-प्लेस हीप निर्माण रूटीन है, जबकि दूसरा कार्यान्वयन के लिए एक सामान्य सबरूटीन है <code>heapify</code>.
   ''(Put elements of 'a' in heap order, in-place)''
   '''procedure''' heapify(a, count) '''is'''
@@ Line 95: / Line 93: @@
    '''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|सिफ्टडाउन संस्करण और सिफ्टअप संस्करण के बीच समय जटिलता में अंतर।]]यह भी <code>siftDown</code> heapify बाइनरी हीप का संस्करण#एक ढेर बनाना|है {{math|''O''(''n'')}} समय जटिलता, जबकि <code>siftUp</code> नीचे दिया गया संस्करण है {{math|''O''(''n'' log ''n'')}} प्रत्येक तत्व को एक समय में एक खाली ढेर में डालने के साथ इसकी समानता के कारण समय की जटिलता।<ref>{{cite web|title=प्राथमिकता कतारें|url=http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L10-PQueues.htm|accessdate=24 May 2011}}</ref>
+[[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|siftUp}} कॉल उस नोड की गहराई के साथ बढ़ती है जिस पर कॉल की जाती है। मूल बात यह है कि एक ढेर में उथले नोड्स की तुलना में कई (तेजी से कई) अधिक गहरे नोड होते हैं, ताकि नीचे या उसके पास नोड्स पर किए गए कॉल की लगभग रैखिक संख्या पर siftUp का पूर्ण लॉगरिदमिक रनिंग-टाइम हो सके ढेर का. दूसरी ओर, किसी एक सिफ्टडाउन कॉल के दौरान होने वाले स्वैप की संख्या घट जाती है क्योंकि जिस नोड पर कॉल की जाती है उसकी गहराई बढ़ जाती है। इस प्रकार, जब <code>siftDown</code> <code>heapify</code> प्रारंभ होता है और कॉल कर रहा है <code>siftDown</code> नीचे और सबसे असंख्य नोड-परतों पर, प्रत्येक सिफ्टिंग कॉल में, अधिक से अधिक, उस नोड की ऊंचाई (ढेर के नीचे से) के बराबर कई स्वैप लगेंगे, जिस पर सिफ्टिंग कॉल की जाती है। दूसरे शब्दों में, लगभग आधी कॉलें {{code|siftDown}} में अधिकतम केवल एक स्वैप होगा, फिर लगभग एक चौथाई कॉल में अधिकतम दो स्वैप होंगे, आदि।
+इस प्रकार, जब <code>siftDown</code> <code>heapify</code>  प्रारंभ होती है और नीचे सिफ़्ट को बुलाती है तब सबसे निचले और सबसे अधिक संख्यामय नोड-परतों पर, प्रत्येक सिफ़्टिंग कॉल पर, अधिकतम एक "ऊंचाई" के समान स्वैप की संख्या हो सकती है। दूसरे शब्दों में, लगभग आधी कॉल {{code|siftDown}}की संख्या में अधिकतम केवल एक स्वैप होगी, फिर लगभग चौथाई कॉल में अधिकतम दो स्वैप होंगे, आदि।
-हीपसॉर्ट एल्गोरिदम में ही है {{math|''O''(''n'' log ''n'')}} heapify के किसी भी संस्करण का उपयोग करके समय जटिलता।
+स्वयं हीपसॉर्ट कलन विधि की दोनों <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
@@ Line 120: / Line 121: @@
                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> प्रक्रिया के बाद से siftUp मानता है कि स्वैप किया जा रहा तत्व अपने अंतिम स्थान पर समाप्त होता है, जबकि siftDown ढेर में नीचे की वस्तुओं के निरंतर समायोजन की अनुमति देता है जब तक कि अपरिवर्तनीय संतुष्ट न हो जाए। उपयोग के लिए समायोजित स्यूडोकोड <code>siftUp</code> दृष्टिकोण नीचे दिया गया है.
+ध्यान दें कि <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''
@@ Line 142: / Line 143: @@
 ==विविधताएं==
-=== फ़्लॉइड का ढेर निर्माण ===
+=== फ्लोयड का हीप निर्माण ===
-बुनियादी एल्गोरिदम का सबसे महत्वपूर्ण बदलाव, जो सभी व्यावहारिक कार्यान्वयन में शामिल है, फ़्लॉइड द्वारा एक ढेर-निर्माण एल्गोरिदम है जो चलता है {{math|''O''(''n'')}} समय और बाइनरी हीप#इंसर्ट के बजाय बाइनरी हीप#एक्सट्रैक्ट का उपयोग करता है, जिससे सिफ्टअप को लागू करने की आवश्यकता से बचा जा सकता है।
+सामान्य कलन विधि की सभी व्यावहारिक कार्यान्वयनों में सम्मिलित सबसे महत्वपूर्ण विभिन्नता है फ्लोयड द्वारा संचालित हीप-निर्माण कलन विधि जो {{math|''O''(''n'')}} समय में चलता है और <code>siftDown</code> का उपयोग करता है, <code>siftUp</code> को पूरी तरह से लागू करने की आवश्यकता से बचता है।
+फ्लोयड के कलन विधि में, एक छोटे से हीप का प्रारंभ करके पत्तियों को बार-बार जोड़ने की जगह, यह पत्तियों से प्रारंभ करता है, जो अपने-आप में तत्व होते हैं और स्वतः ही छोटे से हीप होते हैं। इसके बाद माता-पिता तत्वों को जोड़ता है। {{mvar|n}}/2 से प्रारंभ करके पिछले काम करते हुए, प्रत्येक आंतरिक बिन्दु को <code>siftDown</code> के द्वारा एक वैध हीप का रूट बनाया जाता है। अंतिम चरण है पहले तत्व को सिफ़्टडाउन करना, इसके बाद पूरे सारणी में हीप गुण का पालन किया जाता है।
-एक तुच्छ ढेर से शुरू करने और बार-बार पत्तियों को जोड़ने के बजाय, फ्लोयड का एल्गोरिदम पत्तियों से शुरू होता है, यह देखते हुए कि वे अपने आप में तुच्छ परंतु वैध ढेर हैं, और फिर माता-पिता को जोड़ता है। तत्व से प्रारंभ {{math|''n''/2}} और पीछे की ओर काम करते हुए, प्रत्येक आंतरिक नोड को नीचे छानकर एक वैध ढेर की जड़ बना दिया जाता है। अंतिम चरण पहले तत्व को छानना है, जिसके बाद संपूर्ण सरणी ढेर संपत्ति का पालन करती है।
+फ्लोयड के हीप-निर्माण चरण के दौरान हीपसॉर्ट के सबसे अमान्य स्थितियों में तुलनात्मक संख्या तुलनाएं जानी जाती हैं जो {{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'')}} नंबर के पश्चात्तल शून्य बिटों की संख्या होती है।
-फ्लोयड के हीप-निर्माण चरण के हीपसॉर्ट के दौरान तुलनाओं की सबसे खराब स्थिति वाली संख्या के बराबर मानी जाती है {{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'')}} अनुवर्ती 0 बिट्स की संख्या है।<ref>{{cite journal
+<ref>{{cite journal
   | last1 = Suchenek | first1 = Marek A.
   | title = Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program
@@ Line 155: / Line 158: @@
   | volume = 120
   | issue = 1
-  | year = 2012}}</ref>
+  | 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>
-फ्लोयड के हीप-कंस्ट्रक्शन एल्गोरिदम के मानक कार्यान्वयन के कारण डेटा का आकार [[सीपीयू कैश]] से अधिक हो जाने पर बड़ी संख्या में [[कैश मिस]] हो जाता है।{{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'')}} तुलना सबसे ख़राब स्थिति में और औसतन,{{r|Wegener}} बॉटम-अप वैरिएंट की आवश्यकता है {{math|''n'' log<sub>2</sub>''n'' + ''O''(1)}} औसतन तुलना,{{r|Wegener}} और {{math|1.5''n'' log<sub>2</sub>''n'' + ''O''(''n'')}} सबसे खराब स्थिति में।{{r|fleischer}}
+बॉटम-अप हीपसॉर्ट एक परिवर्तन है जो आवश्यक तुलनाएं कम करने में अहम भूमिका निभाता है। साधारण हीपसॉर्ट में, सबसे अमान्य     स्थितियों में और औसत में  {{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}}
-यदि तुलना सस्ती है (जैसे पूर्णांक कुंजियाँ) तो अंतर महत्वहीन है,{{r|Melhorn}} क्योंकि टॉप-डाउन हीप्सॉर्ट उन मानों की तुलना करता है जो पहले ही मेमोरी से लोड किए जा चुके हैं। हालाँकि, यदि तुलना के लिए [[फ़ंक्शन कॉल]] या अन्य जटिल तर्क की आवश्यकता होती है, तो बॉटम-अप हीप्सॉर्ट लाभप्रद है।
+यदि तुलनाएं निम्न होती हैं, तो यह अंतर नगण्य होता है, क्योंकि टॉप-डाउन हीपसॉर्ट में मैमोरी से लोड किए गए मानों की तुलना की जाती है। यद्यपि, यदि तुलनाएं फलन कॉल या अन्य जटिल तर्क की आवश्यकता होती है, तो बॉटम-अप हीपसॉर्ट लाभप्रद होता है।
-यह सुधार करके पूरा किया गया है <code>siftDown</code> प्रक्रिया। परिवर्तन से रैखिक-समय ढेर-निर्माण चरण में कुछ हद तक सुधार होता है,{{r|McDiarmid}} परंतु दूसरे चरण में अधिक महत्वपूर्ण है। सामान्य हीप्सॉर्ट की तरह, दूसरे चरण का प्रत्येक पुनरावृत्ति ढेर के शीर्ष को निकालता है, {{math|''a''[0]}}, और इसके द्वारा छोड़े गए अंतर को भरता है {{math|''a''[''end'']}}, फिर इस बाद वाले तत्व को ढेर के नीचे छानता है। परंतु यह तत्व ढेर के सबसे निचले स्तर से आता है, जिसका अर्थ है कि यह ढेर में सबसे छोटे तत्वों में से एक है, इसलिए इसे वापस नीचे ले जाने के लिए छानने वाले को कई कदम उठाने पड़ेंगे।<ref name=MacKay05>{{cite web
+यह सुधार करके पूरा किया गया है <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
@@ Line 170: / Line 173: @@
   |url=https://inference.org.uk/mackay/sorting/sorting.html
   |access-date=2021-02-12
-}}</ref> सामान्य हीपसॉर्ट में, सिफ्ट-डाउन के प्रत्येक चरण में न्यूनतम तीन तत्वों को खोजने के लिए दो तुलनाओं की आवश्यकता होती है: नया नोड और उसके दो बच्चे।
+}}</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>
+इसके अतिरिक्त बॉटम-अप का उपयोग करके हीपसॉर्ट को पृथक करता है, पता लगाने के लिए लॉग करता है कि ट्री के पत्ते स्तर तक सबसे बड़े नोंड का मार्ग क्या है केवल प्रति स्तर एक तुलना का उपयोग करके दूसरे विधि से कहें तो, यह एक पत्ता खोजता है जिसका यह गुण होता है कि यह और इसके सभी पूर्वज उनके भाईबंधों से अधिक या उसके समान होते हैं। पुनः इस पत्ते से, यह ऊपरी ओर खोज करता है उस मार्ग में सही स्थान के लिए {{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>
-क्योंकि यह नीचे तक जाता है और फिर वापस ऊपर आता है, इसे कुछ लेखकों द्वारा बाउंस के साथ हीपसॉर्ट कहा जाता है।<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'''
@@ Line 186: / Line 187: @@
           j ← iLeftChild(j)
       '''return''' j
-का वापसी मूल्य <code>leafSearch</code> संशोधित में प्रयोग किया जाता है <code>siftDown</code> दिनचर्या:<ref name="fleischer"/>लीफ़सर्च का रिटर्न मान संशोधित सिफ्टडाउन रूटीन में उपयोग किया जाता है
+<code>leafSearch</code> का रिटर्न मान संशोधित  <code>siftDown</code> रूटीन में उपयोग किया जाता है
        '''procedure''' siftDown(a, i, end) '''is'''                                                                                                                j ← leafSearch(a, i, end)
       '''while''' a[i] > a[j] '''do'''
@@ Line 195: / Line 196: @@
           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/>}}
+बॉटम-अप हीपसॉर्ट को ≥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/>}}
+में इस कलन-विधि के पुनर्मूल्यांकन से पता चला कि यह पूर्णांक कुंजियों के लिए सामान्य हीपसॉर्ट से अधिक तेज़ नहीं है, संभवतः इसलिए क्योंकि आधुनिक [[शाखा भविष्यवाणी|शाखा]]  पूर्वानुमानित तुलनाओं की लागत को कम कर देती है जिससे बॉटम-अप हीपसॉर्ट बचने का प्रबंधन करता है।<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>
-में इस एल्गोरिथ्म के पुनर्मूल्यांकन से पता चला कि यह पूर्णांक कुंजियों के लिए सामान्य हीपसॉर्ट से अधिक तेज़ नहीं है, संभवतः इसलिए क्योंकि आधुनिक [[शाखा भविष्यवाणी]] पूर्वानुमानित तुलनाओं की लागत को कम कर देती है जिससे बॉटम-अप हीपसॉर्ट बचने का प्रबंधन करता है।<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>
-एक वैरिएंट जो प्रति आंतरिक नोड दो अतिरिक्त बिट्स का उपयोग करता है (एन-तत्व ढेर के लिए कुल एन-1 बिट्स) यह जानकारी कैश करने के लिए कि कौन सा बच्चा बड़ा है (तीन मामलों को संग्रहीत करने के लिए दो बिट्स की आवश्यकता होती है: बाएं, दाएं और अज्ञात)<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>
 === अन्य विविधताएँ ===
-*[[ त्रिगुट ढेर ]]्सॉर्ट बाइनरी हीप के बजाय टर्नरी हीप का उपयोग करता है; अर्थात्, ढेर में प्रत्येक तत्व के तीन बच्चे हैं। इसे प्रोग्राम करना अधिक जटिल है, परंतु यह लगातार कई गुना कम स्वैप और तुलनात्मक संचालन करता है। ऐसा इसलिए है क्योंकि टर्नरी हीप में प्रत्येक सिफ्ट-डाउन चरण के लिए तीन तुलनाओं और एक स्वैप की आवश्यकता होती है, जबकि बाइनरी हीप में दो तुलनाओं और एक स्वैप की आवश्यकता होती है। एक टर्नरी ढेर कवर में दो स्तर 3<sup>2</sup>=9 तत्व, बाइनरी हीप में तीन स्तरों के समान तुलनाओं के साथ अधिक काम करते हैं, जो केवल 2 को कवर करते हैं<sup>3</sup>=8.{{Citation needed|date=September 2014}} यह मुख्य रूप से अकादमिक रुचि का है, या एक छात्र अभ्यास के रूप में,<ref>{{cite book
+*[[ त्रिगुट ढेर |त्रिगुट हीप]] एक त्रिधातु हीप का उपयोग करता है बाइनरी हीप के अतिरिक्त अर्थात प्रत्येक हीप में तीन वंशज होते हैं। {{r|MacKay05}}इसे प्रोग्राम करना अधिक जटिल होता है, परंतु यह स्वैप और तुलना कार्यों को एक स्थिर संख्या को कम करता है। इसका कारण है कि टर्नरी हीप में प्रत्येक सिफ्ट-डाउन चरण में तीन तुलनाएं और एक स्वैप की आवश्यकता होती है, जबकि बाइनरी हीप में दो तुलनाएं और एक स्वैप की आवश्यकता होती है। टर्नरी हीप में दो स्तर द्वारा 32 = 9 तत्वों को कवर किया जाता है, जबकि बाइनरी हीप में तीन स्तरों द्वारा केवल 23 = 8 कवर किए जाते हैं।, क्योंकि अतिरिक्त जटिलता मान्य बचत से योग्य नहीं होती है, और नीचे से ऊपर हीपसॉर्ट दोनों को पीछे छोड़ता है।
- |title=Data Structures Using Pascal
+*मेमोरी-अनुकूल हीपसॉर्ट{{r|LaMarca99|p=87}}  से यह संदर्भ की स्थानिकता को बढ़ाकर हीपसॉर्ट की सुधार की गई है। इससे तुलनाएं बढ़ जाती हैं, परंतु क्योंकि सभी वंशज क्रमशः मेमोरी में संग्रहीत होते हैं, इसलिए हीप यात्रा के समय एक्सेस किए जाने वाले कैश लाइनों की संख्या को कम करता है, जो एक नेट प्रदर्शन में सुधार करता है।
- |chapter=Chapter 8: Sorting
- |first1=Aaron M. |last1=Tenenbaum
- |first2=Moshe J. |last2=Augenstein
- |year=1981
- |page=405
- |isbn=0-13-196501-8
- |quote=<!--Exercise 8. Define an almost complete ternary tree as a tree in which every node has at most three sons and such that the nodes can be numbered from 1 to n so that the sons of node[i] are node[3*i−l], node[3*i] and node[3*i+l]. Define a ternary heap as an almost complete ternary tree in which the content of each node is greater than or equal to the contents of all its descendants. -->Write a sorting routine similar to the heapsort except that it uses a ternary heap.
-}}</ref> क्योंकि अतिरिक्त जटिलता मामूली बचत के लायक नहीं है, और बॉटम-अप हीपसॉर्ट दोनों को मात देता है।
-*मेमोरी-अनुकूलित हीपसॉर्ट{{r|LaMarca99|p=87}} बच्चों की संख्या को और अधिक बढ़ाकर हीपसॉर्ट के संदर्भ स्थान में सुधार करता है। इससे तुलनाओं की संख्या बढ़ जाती है, परंतु चूंकि सभी बच्चों को मेमोरी में लगातार संग्रहीत किया जाता है, इसलिए हीप ट्रैवर्सल के दौरान एक्सेस की गई [[कैश लाइन]]ों की संख्या कम हो जाती है, जिससे शुद्ध प्रदर्शन में सुधार होता है।
 * जगह से बाहर हीप्सॉर्ट<ref>{{cite conference
   |title=QuickHeapsort, an efficient mix of classical sorting algorithms
@@ Line 235: / Line 230: @@
   |zbl=1016.68042
   |url=https://core.ac.uk/download/pdf/81957449.pdf
-}}</ref>{{r|MacKay05}} सबसे खराब स्थिति को समाप्त करके बॉटम-अप हीप्सॉर्ट में सुधार करता है, गारंटी देता है {{math|''n'' log<sub>2</sub>''n'' + ''O''(''n'')}} तुलना. जब अधिकतम लिया जाता है, तो रिक्त स्थान को अवर्गीकृत डेटा मान से भरने के बजाय, इसे a से भरें {{math|−∞}} प्रहरी मूल्य, जो कभी भी वापस ऊपर नहीं लौटता। यह पता चला है कि इसे इन-प्लेस (और गैर-पुनरावर्ती) क्विकहेप्सॉर्ट एल्गोरिदम में एक आदिम के रूप में उपयोग किया जा सकता है।<ref>{{cite journal
+}}</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
@@ Line 245: / Line 240: @@
 <!-- |doi=10.1007/978-3-642-38536-0_3 Conference version, published September 2012-->
   |arxiv=1209.4214
-|s2cid=792585 }}</ref> सबसे पहले, आप एक क्विकसॉर्ट-जैसा विभाजन पास करते हैं, परंतु सरणी में विभाजित डेटा के क्रम को उलट देते हैं। मान लीजिए (सामान्यता की हानि के बिना) कि छोटा विभाजन धुरी से बड़ा है, जिसे सरणी के अंत में जाना चाहिए, परंतु हमारा उलटा विभाजन चरण इसे शुरुआत में रखता है। छोटे विभाजन से एक ढेर बनाएं और उस पर जगह से बाहर हीप्सॉर्ट करें, निकाले गए मैक्सिमा को सरणी के अंत से मूल्यों के साथ बदलें। ये धुरी से कम हैं, अर्थात ढेर में किसी भी मूल्य से कम हैं, इसलिए इस रूप में कार्य करें {{math|−∞}} प्रहरी मान. एक बार जब हीपसॉर्ट पूरा हो जाता है (और धुरी को सरणी के अब-क्रमबद्ध अंत से ठीक पहले ले जाया जाता है), विभाजन का क्रम उलट दिया गया है, और सरणी की शुरुआत में बड़े विभाजन को उसी तरह से क्रमबद्ध किया जा सकता है। (क्योंकि कोई नॉन-[[ पूँछ प्रत्यावर्तन ]] नहीं है, यह क्विकसॉर्ट को भी खत्म कर देता है {{math|''O''(log ''n'')}} स्टैक उपयोग।)
+|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'')}} प्रारंभिक क्रमबद्ध स्थिति की परवाह किए बिना। इसकी जटिलता के कारण, स्मूथसॉर्ट का उपयोग शायद ही कभी किया जाता है।{{citation needed|date=November 2016}}
+*[[स्मूथसॉर्ट]] कलन विधि<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
@@ Line 258: / Line 253: @@
   | 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>{{cite web
+  }} {{Q|56049336}}.</ref> कार्टेशियन ट्री के हीप के आधार पर हीपो की विविधता का वर्णन करें। सबसे पहले, एक कार्टेशियन ट्री इनपुट से बनाया गया है {{math|''O''(''n'')}} समय, और इसकी रूट को 1-तत्व बाइनरी हीप में रखा गया है। पुनः हम बार-बार बाइनरी हीप से न्यूनतम निकालते हैं, ट्री के मूल तत्व को आउटपुट करते हैं, और उसके बाएं और दाएं रूट को बाइनरी हीप में जोड़ते हैं, जो स्वयं कार्टेशियन ट्री हैं।<ref name=":0">{{cite web
   |title=CartesianTreeSort.hh
   |website=Archive of Interesting Code
@@ Line 264: / Line 259: @@
   |first=Keith |last=Schwartz
   |date=27 December 2010 |access-date=2019-03-05
-}}</ref> जैसा कि वे दिखाते हैं, यदि इनपुट पहले से ही लगभग सॉर्ट किया गया है, तो कार्टेशियन पेड़ बहुत असंतुलित होंगे, कुछ नोड्स में बाएं और दाएं बच्चे होंगे, जिसके परिणामस्वरूप बाइनरी ढेर छोटा रहेगा, और एल्गोरिदम को अधिक तेज़ी से सॉर्ट करने की अनुमति मिलेगी {{math|''O''(''n'' log ''n'')}} उन इनपुट के लिए जो पहले से ही लगभग क्रमबद्ध हैं।
+}}</ref> जैसा कि वे दिखाते हैं, यदि इनपुट पहले से ही छोटा किया गया है, तो कार्टेशियन ट्री बहुत असंतुलित होंगे, कुछ नोड्स में बाएं और दाएं रूट होंगे, जिसके परिणामस्वरूप बाइनरी हीप छोटा रहेगा, और कलन विधि को अधिक तेज़ी से सॉर्ट करने की अनुमति मिलेगी उन इनपुट के लिए {{math|''O''(''n'' log ''n'')}} जो पहले से ही लगभग क्रमबद्ध हैं।
-* Weak heap#Weak-heap sort जैसे कई वेरिएंट की आवश्यकता होती है {{math|''n'' log<sub>2</sub> ''n''+''O''(1)}} सबसे खराब स्थिति में तुलना, सैद्धांतिक न्यूनतम के करीब, प्रति नोड राज्य के एक अतिरिक्त बिट का उपयोग करना। हालाँकि यह अतिरिक्त बिट एल्गोरिदम को वास्तव में सही जगह पर नहीं रखता है, यदि इसके लिए तत्व के अंदर जगह मिल सकती है, तो ये एल्गोरिदम सरल और कुशल हैं,{{r|Bojesen00|p=40}} परंतु फिर भी बाइनरी हीप्स की तुलना में धीमी है यदि कुंजी तुलनाएं इतनी सस्ती हैं (उदाहरण के लिए पूर्णांक कुंजी) कि एक स्थिर कारक कोई मायने नहीं रखता।<ref name=Kat2014-11-14P>{{cite conference |title=Seeking for the best priority queue: Lessons learnt |first=Jyrki |last=Katajainen |date=23 September 2013 |conference=Algorithm Engineering (Seminar 13391) |location=Dagstuhl |pages=19–20, 24 |url=http://hjemmesider.diku.dk/~jyrki/Myris/Kat2013-09-23P.html}}</ref>
+* कई प्रकार की विफल हीपसॉर्ट आपत्तिग्रस्त विषय में {{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|''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>)}} सबसे खराब स्थिति, या तो। (सावधानीपूर्वक कार्यान्वयन से उत्तरार्द्ध से बचा जा सकता है, परंतु यह क्विकॉर्ट को और अधिक जटिल बनाता है, और सबसे लोकप्रिय समाधानों में से एक, इंट्रोसॉर्ट, इस उद्देश्य के लिए हीप्सॉर्ट का उपयोग करता है।)
+== अन्य प्रकार से तुलना ==
+हीप्सॉर्ट मुख्य रूप से क्विकसॉर्ट के साथ प्रतिस्पर्धा करता है, जो एक और बहुत ही कुशल सामान्य प्रयोजन इन-प्लेस तुलना-आधारित सॉर्ट कलन विधि है।
-इसका प्राथमिक नुकसान इसके संदर्भ की खराब स्थानीयता और इसकी स्वाभाविक रूप से क्रमिक प्रकृति है; अंतर्निहित पेड़ तक पहुंच व्यापक रूप से बिखरी हुई है और अधिकतर यादृच्छिक है, और इसे [[समानांतर एल्गोरिदम]] में बदलने का कोई सीधा तरीका नहीं है।
+हीपसॉर्ट के प्राथमिक लाभ इसके सरल, गैर-[[रिकर्सन (कंप्यूटर विज्ञान)]] कोड, न्यूनतम सहायक भंडारण आवश्यकता और विश्वसनीय रूप से अच्छा प्रदर्शन हैं: इसके सबसे अच्छे और सबसे अमान्य स्थितियों एक-दूसरे के एक छोटे स्थिर कारक के भीतर हैं, और तुलना की संख्या किसी सूची को क्रमबद्ध करना आवश्यक है. जबकि यह इससे बेहतर नहीं कर सकता {{math|''O''(''n'' log ''n'')}} पूर्व-सॉर्ट किए गए इनपुट के लिए, यह क्विकसॉर्ट से प्रभावित नहीं होता है {{math|''O''(''n''<sup>2</sup>)}} सबसे अमान्य स्थिति, या तो। सावधानीपूर्वक कार्यान्वयन से उत्तरार्द्ध से बचा जा सकता है, परंतु यह क्विकॉर्ट को और अधिक जटिल बनाता है, और सबसे लोकप्रिय समाधानों में से एक, इंट्रोसॉर्ट, इस उद्देश्य के लिए हीप्सॉर्ट का उपयोग करता है।
-यह इसे [[ अंतः स्थापित प्रणाली ]], [[वास्तविक समय कंप्यूटिंग]] और दुर्भावनापूर्ण रूप से चुने गए इनपुट से संबंधित सिस्टम में लोकप्रिय बनाता है,<ref>{{cite web
+इसका प्राथमिक नुकसान इसके संदर्भ की अमान्य स्थानीयता और इसकी स्वाभाविक रूप से क्रमिक प्रकृति है; अंतर्निहित ट्री तक पहुंच व्यापक रूप से बिखरी हुई है और अधिकतर यादृच्छिक है, और इसे [[समानांतर एल्गोरिदम|समानांतर कलन विधि]] में बदलने का कोई सीधा तरीका नहीं है।इसलिए यह [[ अंतः स्थापित प्रणाली |संगठित प्रणालियों]], [[वास्तविक समय कंप्यूटिंग|वास्तविक समय गणना]] में और कुछ विशेष चयनित इनपुट पर ध्यान देने वाले सिस्टमों में लोकप्रिय हो जाता है<ref>{{cite web
   |work=Data Structures and Algorithms
   |title=Comparing Quick and Heap Sorts
@@ Line 284: / Line 277: @@
   |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> यह किसी भी एप्लिकेशन के लिए एक अच्छा विकल्प है, जिसे सॉर्ट करने पर [[ टोंटी (कंप्यूटिंग) ]] की उम्मीद नहीं होती है।
+}}</ref>, जैसे लिनक्स कर्नल इसका चयन करना अच्छा विकल्प है<ref>https://github.com/torvalds/linux/blob/master/lib/sort.c Linux kernel source</ref> यह किसी भी एप्लिकेशन के लिए एक अच्छा विकल्प है, जिसे सॉर्ट करते समय किसी रुकावट की आशा नहीं होती है।एक अच्छी तरह से कार्यान्वित क्विकसॉर्ट सामान्यतः  हीपसॉर्ट के सापेक्ष में 2-3 गुना तेज होता है।<ref name="LaMarca99">{{cite journal
-एक अच्छी तरह से कार्यान्वित क्विकसॉर्ट आमतौर पर हीपसॉर्ट की तुलना में 2-3 गुना तेज होता है।<ref name=LaMarca99>{{cite journal
   |title=The Influence of Caches on the Performance of Sorting
   |first1=Anthony |last1=LaMarca
@@ Line 302: / Line 293: @@
   |date=14 May 2014
   |url=https://www.researchgate.net/publication/228620592
-}} See Fig. 1 on p. 6.</ref> हालाँकि क्विकॉर्ट के लिए कम तुलनाओं की आवश्यकता होती है, यह एक मामूली कारक है। (दोगुने तुलनाओं का दावा करने वाले परिणाम टॉप-डाउन संस्करण को माप रहे हैं; देखें {{section link||Bottom-up heapsort}}.) क्विकसॉर्ट का मुख्य लाभ इसके संदर्भ का बेहतर स्थानीयता है: विभाजन अच्छे स्थानिक इलाके के साथ एक रैखिक स्कैन है, और पुनरावर्ती उपखंड में अच्छा अस्थायी इलाका है। अतिरिक्त प्रयास के साथ, क्विकॉर्ट को ज्यादातर [[शाखा-मुक्त कोड]] में भी लागू किया जा सकता है, और समानांतर में उप-विभाजन को सॉर्ट करने के लिए कई सीपीयू का उपयोग किया जा सकता है। इस प्रकार, जब अतिरिक्त प्रदर्शन कार्यान्वयन प्रयास को उचित ठहराता है तो क्विकॉर्ट को प्राथमिकता दी जाती है।
+}} See Fig. 1 on p. 6.</ref> यद्यपि क्विकॉर्ट  को कम तुलनाएं की आवश्यकता होती है, यह एक छोटा कारक होता है।का मुख्य फायदा उसकी उत्कृष्ट संदर्भ की स्थानिकता है: विभाजन एक रेखीय  स्कैन है जिसमें अच्छी स्थानिकता होती है, और रिकर्सिव विभाजन में अच्छी कालिक स्थानिकता होती है। अतिरिक्त प्रयास के साथ, क्विकसॉर्ट सामान्यतः अधिकांश शाखामुक्त कोड में लागू किया जा सकता है, और उप-भागों को समानांतर में क्रमबद्ध करने के लिए कई सीपीयू का उपयोग किया जा सकता है। इस प्रकार,क्विकसॉर्ट प्राथमिकता दी जाती है जब अतिरिक्त प्रदर्शन को यथार्थ करता है।
-दूसरा प्रमुख {{math|''O''(''n'' log ''n'')}} सॉर्टिंग एल्गोरिदम [[ मर्ज़ सॉर्ट ]] है, परंतु यह शायद ही कभी हीपसॉर्ट के साथ सीधे प्रतिस्पर्धा करता है क्योंकि यह इन-प्लेस नहीं है। मर्ज सॉर्ट की आवश्यकता के लिए {{math|Ω(''n'')}} अतिरिक्त स्थान (इनपुट का लगभग आधा आकार<!--Known techniques for reducing this by a small constant factor omitted for simplicity-->) आमतौर पर उन स्थितियों को छोड़कर निषेधात्मक है जहां मर्ज सॉर्ट का स्पष्ट लाभ होता है:
+दूसरा प्रमुख {{math|''O''(''n'' log ''n'')}} क्रमबद्धीकरण कलन विधि है, परंतु यह साधारणतः हीपसॉर्ट के साथ सीधे प्रतियोगिता नहीं करता है क्योंकि यह इन-प्लेस नहीं होता है। मर्ज सॉर्ट की {{math|Ω(''n'')}} अतिरिक्त स्थान की आवश्यकता सामान्यतः रोकात्मक होती है, केवल वे स्थितियों में नहीं जहां मर्ज सॉर्ट का स्पष्ट लाभ होता है।
-* जब एक स्थिर प्रकार की आवश्यकता होती है
+* जब स्थिर क्रमबद्धता की आवश्यकता होती है
-* (आंशिक रूप से) पूर्व-क्रमबद्ध इनपुट का लाभ उठाते समय
+* जब (आंशिक रूप से) पूर्व-क्रमबद्ध इनपुट का लाभ उठाना होता है
-* लिंक की गई सूचियों को क्रमबद्ध करना (जिस स्थिति में मर्ज सॉर्ट के लिए न्यूनतम अतिरिक्त स्थान की आवश्यकता होती है)
+* युग्मित सूचियाँ को क्रमबद्ध करना (जिसमें मर्ज सॉर्ट को न्यूनतम अतिरिक्त स्थान की आवश्यकता होती है)
-* समानांतर छँटाई; मर्ज सॉर्ट क्विकॉर्ट की तुलना में और भी बेहतर तरीके से समानांतर होता है और आसानी से [[ रैखिक गति ]] के करीब पहुंच सकता है
+* समानांतर क्रमबद्धीकरण;  विलय सॉर्ट क्रमबद्धीकरण से भी बेहतर समानांतर कार्यशील होता है और लगभग रेखांकनीय गति तक प्राप्त कर सकता है
-* [[बाहरी छँटाई]]; मर्ज सॉर्ट में संदर्भ का उत्कृष्ट स्थान है
+* बाहरी क्रमबद्धीकरण;विलय सॉर्ट में संदर्भ की उत्कृष्ट स्थानिकता होती है।
 == उदाहरण ==
-मान लीजिए कि {6, 5, 3, 1, 8, 7, 2, 4 } वह सूची है जिसे हम सबसे छोटे से सबसे बड़े तक क्रमबद्ध करना चाहते हैं। (ध्यान दें, 'बिल्डिंग द हीप' चरण के लिए: बड़े नोड छोटे नोड पैरेंट के नीचे नहीं रहते हैं। उन्हें पैरेंट के साथ स्वैप किया जाता है, और फिर यदि किसी अन्य स्वैप की आवश्यकता होती है, तो पुनरावर्ती रूप से जांच की जाती है, ताकि हीप बाइनरी ट्री पर बड़ी संख्या को छोटी संख्या से ऊपर रखा जा सके। .)
+हम निम्नलिखित चरणों का पालन करके सूची { 6, 5, 3, 1, 8, 7, 2, 4 } को सबसे छोटे से सबसे बड़े तक क्रमबद्ध करने के लिए हीपसॉर्ट एल्गोरिदम का प्रयोग कर सकते हैं। ध्यान दें, 'हीप निर्माण' चरण के लिए: बड़े नोड छोटे बिन्दु पैरेंट के नीचे रहने के अतिरिक्त पैरेंट के साथ स्वैप किए जाते हैं, और फिर पुनरावृत्ति से यदि आवश्यक हो तो जांचा जाता है कि एक और स्वैप की आवश्यकता है, जिससे हीप द्विआधारी ट्री पर बड़े नंबरों को छोटे नंबरों से ऊपर रखा जा सके।
 [[File:Heapsort-example.gif|350px|thumb|right|हीप्सॉर्ट पर एक उदाहरण.]]
-=== ढेर बनाएँ ===
+=== हीप  बनाएँ ===
 {| class="wikitable"
@@ Line 358: / Line 349: @@
 !तत्वों की अदला-बदली करें
 !तत्व हटाएँ
-!क्रमबद्ध सरणी
+!क्रमबद्ध सारणी
 !विवरण
 |-
-| '''8''', 6, 7, 4, 5, 3, 2, '''1''' || 8, 1 ||   ||   ||ढेर से 8 हटाने के लिए 8 और 1 की अदला-बदली करें
+| '''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, '''8''' ||   || 8 ||   ||हीप  से 8 हटाएं और क्रमबद्ध सारणी     में जोड़ें
 |-
-| '''1''', 6, '''7''', 4, 5, 3, 2 || 1, 7 ||   || style="text-align: right;" | 8 ||1 और 7 को स्वैप करें क्योंकि वे ढेर में क्रम में नहीं हैं
+| '''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, '''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 की अदला-बदली करें
+| '''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, '''7'''       ||      || 7 || style="text-align: right;" | 8 ||हीप  से 7 हटाएं और क्रमबद्ध सारणी     में जोड़ें
 |-
-| '''2''', '''6''', 3, 4, 5, 1 || 2, 6 ||   || style="text-align: right;" | 7, 8 ||2 और 6 को स्वैप करें क्योंकि वे ढेर में क्रम में नहीं हैं
+| '''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, '''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 की अदला-बदली करें
+| '''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, '''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 को स्वैप करें क्योंकि वे ढेर में क्रम में नहीं हैं
+| '''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, '''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 की अदला-बदली करें
+| '''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, '''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 को स्वैप करें क्योंकि वे ढेर में क्रम में नहीं हैं
+| '''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 की अदला-बदली करें
+| '''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, '''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 को स्वैप करें क्योंकि वे ढेर में क्रम में नहीं हैं
+| '''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 की अदला-बदली करें
+| '''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, '''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 को स्वैप करें क्योंकि वे ढेर में क्रम में नहीं हैं
+| '''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 की अदला-बदली करें
+| '''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, '''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 हटाएं और क्रमबद्ध सरणी में जोड़ें
+| '''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}}
@@ Line 438: / Line 429: @@
 {{sorting}}
-[[Category: स्यूडोकोड उदाहरण सहित लेख]] [[Category: तुलना प्रकार]] [[Category: ढेर (डेटा संरचनाएं)]] [[Category: छँटाई एल्गोरिदम]]
-[[Category: Machine Translated Page]]
+[[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:स्यूडोकोड उदाहरण सहित लेख]]

Anonymous

Search

हीपसॉर्ट: Difference between revisions

Latest revision as of 18:18, 16 July 2023

अवलोकन

कलन विधि

छद्मकोड

विविधताएं

फ्लोयड का हीप निर्माण

बॉटम-अप हीप्सॉर्ट

अन्य विविधताएँ

अन्य प्रकार से तुलना

उदाहरण

हीप बनाएँ

छँटाई

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories