हीपसॉर्ट

हीपसॉर्ट

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

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

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

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

अवलोकन

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

पहले चरण में, डेटा से हीप बनाया जाता है। हीप प्रायः पूर्ण बाइनरी ट्री विन्यास के साथ एक सरणी में रखा जाता है। संपूर्ण बाइनरी ट्री, बाइनरी ट्री संरचना को सरणी सूचकांकों में मैप करता है; प्रत्येक सरणी सूचकांक एक नोड का प्रतिनिधित्व करता है; नोड के मूल, बाईं चाइल्ड शाखा, या दाईं चाइल्ड शाखा का सूचकांक सरल अभिव्यक्ति हैं। शून्य-आधारित सरणी के लिए, रूट नोड को सूचकांक 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

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

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

कलन विधि

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

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

चरण हैं:

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

छद्मकोड

स्यूडोकोड में कलन विधि को लागू करने का एक सरल तरीका निम्नलिखित है। ऐरे प्रोग्रामिंग भाषाओं (सरणी) की तुलना हैं|शून्य-आधारित और swap सरणी के दो तत्वों का आदान-प्रदान करने के लिए उपयोग किया जाता है। 'नीचे' गति का अर्थ है जड़ से पत्तियों की ओर, या निम्न सूचकांक से उच्चतर की ओर। ध्यान दें कि सॉर्ट के दौरान, सबसे बड़ा तत्व हीप के मूल में होता है 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.

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

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

यह भी siftDown heapify बाइनरी हीप का संस्करण#एक हीप बनाना|है O(n) समय जटिलता, जबकि siftUp नीचे दिया गया संस्करण है O(n log n) प्रत्येक तत्व को एक समय में एक खाली हीप में डालने के साथ इसकी समानता के कारण समय की जटिलता।

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

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

हीपसॉर्ट कलन विधि में ही है O(n log n) heapify के किसी भी संस्करण का उपयोग करके समय जटिलता।

     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) समय और बाइनरी हीप#इंसर्ट के बजाय बाइनरी हीप#एक्सट्रैक्ट का उपयोग करता है, जिससे सिफ्टअप को लागू करने की आवश्यकता से बचा जा सकता है।

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

फ्लोयड के हीप-निर्माण चरण के हीपसॉर्ट के दौरान तुलनाओं की सबसे खराब स्थिति वाली संख्या के बराबर मानी जाती है 2n − 2s₂(n) − e₂(n), कहाँ s₂(n) बाइनरी प्रतिनिधित्व में 1 बिट्स की संख्या है n और e₂(n) अनुवर्ती 0 बिट्स की संख्या है। फ्लोयड के हीप-कंस्ट्रक्शन कलन विधि के मानक कार्यान्वयन के कारण डेटा का आकार सीपीयू कैश से अधिक हो जाने पर बड़ी संख्या में कैश मिस हो जाता है। ऊपर वाले स्तर पर आगे बढ़ने से पहले सभी उपहीप्स को एक स्तर पर संयोजित करने के बजाय, जितनी जल्दी हो सके सबहीप्स को मिलाकर, गहराई-पहले क्रम में विलय करके बड़े डेटा सेट पर बेहतर प्रदर्शन प्राप्त किया जा सकता है।

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

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

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

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

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

    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 आकार के सरणियों पर बीटिंग क्विकसॉर्ट (तीन धुरी चयन के मध्य के साथ) के रूप में घोषित किया गया था।

2008 में इस एल्गोरिथ्म के पुनर्मूल्यांकन से पता चला कि यह पूर्णांक कुंजियों के लिए सामान्य हीपसॉर्ट से अधिक तेज़ नहीं है, संभवतः इसलिए क्योंकि आधुनिक शाखा भविष्यवाणी पूर्वानुमानित तुलनाओं की लागत को कम कर देती है जिससे बॉटम-अप हीपसॉर्ट बचने का प्रबंधन करता है। एक और परिशोधन चयनित पत्ते के पथ में एक द्विआधारी खोज करता है, और सबसे खराब स्थिति में सॉर्ट करता है (n+1)(log₂(n+1) + log₂ log₂(n+1) + 1.82) + O(log₂n) तुलना, तुलनात्मक प्रकार के निकट#किसी सूची को क्रमबद्ध करने के लिए आवश्यक तुलनाओं की संख्या|सूचना-सैद्धांतिक निचली सीमा n log₂n − 1.4427n तुलना. एक वैरिएंट जो प्रति आंतरिक नोड दो अतिरिक्त बिट्स का उपयोग करता है (एन-तत्व हीप के लिए कुल एन-1 बिट्स) यह जानकारी कैश करने के लिए कि कौन सा बच्चा बड़ा है (तीन मामलों को संग्रहीत करने के लिए दो बिट्स की आवश्यकता होती है: बाएं, दाएं और अज्ञात) से कम उपयोग करता है n log₂n + 1.1n तुलना करता है.

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

• त्रिगुट हीप ्सॉर्ट बाइनरी हीप के बजाय टर्नरी हीप का उपयोग करता है; अर्थात्, हीप में प्रत्येक तत्व के तीन बच्चे हैं। इसे प्रोग्राम करना अधिक जटिल है, परंतु यह लगातार कई गुना कम स्वैप और तुलनात्मक संचालन करता है। ऐसा इसलिए है क्योंकि टर्नरी हीप में प्रत्येक सिफ्ट-डाउन चरण के लिए तीन तुलनाओं और एक स्वैप की आवश्यकता होती है, जबकि बाइनरी हीप में दो तुलनाओं और एक स्वैप की आवश्यकता होती है। एक टर्नरी हीप कवर में दो स्तर 3²=9 तत्व, बाइनरी हीप में तीन स्तरों के समान तुलनाओं के साथ अधिक काम करते हैं, जो केवल 2 को कवर करते हैं³=8. यह मुख्य रूप से अकादमिक रुचि का है, या एक छात्र अभ्यास के रूप में, क्योंकि अतिरिक्त जटिलता मामूली बचत के लायक नहीं है, और बॉटम-अप हीपसॉर्ट दोनों को मात देता है।
• मेमोरी-अनुकूलित हीपसॉर्ट बच्चों की संख्या को और अधिक बढ़ाकर हीपसॉर्ट के संदर्भ स्थान में सुधार करता है। इससे तुलनाओं की संख्या बढ़ जाती है, परंतु चूंकि सभी बच्चों को मेमोरी में लगातार संग्रहीत किया जाता है, इसलिए हीप ट्रैवर्सल के दौरान एक्सेस की गई कैश लाइनों की संख्या कम हो जाती है, जिससे शुद्ध प्रदर्शन में सुधार होता है।
• जगह से बाहर हीप्सॉर्ट सबसे खराब स्थिति को समाप्त करके बॉटम-अप हीप्सॉर्ट में सुधार करता है, गारंटी देता है n log₂n + O(n) तुलना. जब अधिकतम लिया जाता है, तो रिक्त स्थान को अवर्गीकृत डेटा मान से भरने के बजाय, इसे a से भरें −∞ प्रहरी मूल्य, जो कभी भी वापस ऊपर नहीं लौटता। यह पता चला है कि इसे इन-प्लेस (और गैर-पुनरावर्ती) क्विकहेप्सॉर्ट कलन विधि में एक आदिम के रूप में उपयोग किया जा सकता है। सबसे पहले, आप एक क्विकसॉर्ट-जैसा विभाजन पास करते हैं, परंतु सरणी में विभाजित डेटा के क्रम को उलट देते हैं। मान लीजिए (सामान्यता की हानि के बिना) कि छोटा विभाजन धुरी से बड़ा है, जिसे सरणी के अंत में जाना चाहिए, परंतु हमारा उलटा विभाजन चरण इसे शुरुआत में रखता है। छोटे विभाजन से एक हीप बनाएं और उस पर जगह से बाहर हीप्सॉर्ट करें, निकाले गए मैक्सिमा को सरणी के अंत से मूल्यों के साथ बदलें। ये धुरी से कम हैं, अर्थात हीप में किसी भी मूल्य से कम हैं, इसलिए इस रूप में कार्य करें −∞ प्रहरी मान. एक बार जब हीपसॉर्ट पूरा हो जाता है (और धुरी को सरणी के अब-क्रमबद्ध अंत से ठीक पहले ले जाया जाता है), विभाजन का क्रम उलट दिया गया है, और सरणी की शुरुआत में बड़े विभाजन को उसी तरह से क्रमबद्ध किया जा सकता है। (क्योंकि कोई नॉन-पूँछ प्रत्यावर्तन नहीं है, यह क्विकसॉर्ट को भी खत्म कर देता है O(log n) स्टैक उपयोग।)
• स्मूथसॉर्ट कलन विधि 1981 में एड्सगर डब्ल्यू डिज्क्स्ट्रा द्वारा विकसित हीप्सॉर्ट का एक रूप है। हीप्सॉर्ट की तरह, स्मूथसॉर्ट की ऊपरी सीमा है O(n log n). स्मूथसॉर्ट का लाभ यह है कि यह करीब आता है O(n) समय यदि अनुकूली प्रकार है, जबकि हीपसॉर्ट औसत है O(n log n) प्रारंभिक क्रमबद्ध स्थिति की परवाह किए बिना। इसकी जटिलता के कारण, स्मूथसॉर्ट का उपयोग शायद ही कभी किया जाता है।
• लेवकोपोलोस और पीटरसन कार्टेशियन पेड़ों के हीप के आधार पर हीप ों की विविधता का वर्णन करें। सबसे पहले, एक कार्टेशियन पेड़ इनपुट से बनाया गया है O(n) समय, और इसकी जड़ को 1-तत्व बाइनरी हीप में रखा गया है। फिर हम बार-बार बाइनरी हीप से न्यूनतम निकालते हैं, पेड़ के मूल तत्व को आउटपुट करते हैं, और उसके बाएं और दाएं बच्चों (यदि कोई हो) को बाइनरी हीप में जोड़ते हैं, जो स्वयं कार्टेशियन पेड़ हैं। जैसा कि वे दिखाते हैं, यदि इनपुट पहले से ही लगभग सॉर्ट किया गया है, तो कार्टेशियन पेड़ बहुत असंतुलित होंगे, कुछ नोड्स में बाएं और दाएं बच्चे होंगे, जिसके परिणामस्वरूप बाइनरी हीप छोटा रहेगा, और कलन विधि को अधिक तेज़ी से सॉर्ट करने की अनुमति मिलेगी O(n log n) उन इनपुट के लिए जो पहले से ही लगभग क्रमबद्ध हैं।
• Weak heap#Weak-heap sort जैसे कई वेरिएंट की आवश्यकता होती है n log₂ n+O(1) सबसे खराब स्थिति में तुलना, सैद्धांतिक न्यूनतम के करीब, प्रति नोड राज्य के एक अतिरिक्त बिट का उपयोग करना। हालाँकि यह अतिरिक्त बिट कलन विधि को वास्तव में सही जगह पर नहीं रखता है, यदि इसके लिए तत्व के अंदर जगह मिल सकती है, तो ये कलन विधि सरल और कुशल हैं, परंतु फिर भी बाइनरी हीप्स की तुलना में धीमी है यदि कुंजी तुलनाएं इतनी सस्ती हैं (उदाहरण के लिए पूर्णांक कुंजी) कि एक स्थिर कारक कोई मायने नहीं रखता।
• काटाजाइनेन के अंतिम हेप्सॉर्ट को किसी अतिरिक्त भंडारण की आवश्यकता नहीं है, प्रदर्शन करता है n log₂ n+O(1) तुलना, और समान संख्या में तत्व चलते हैं। हालाँकि, यह और भी अधिक जटिल है और तब तक उचित नहीं है जब तक तुलनाएँ बहुत महंगी न हों।

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

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

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

इसका प्राथमिक नुकसान इसके संदर्भ की खराब स्थानीयता और इसकी स्वाभाविक रूप से क्रमिक प्रकृति है; अंतर्निहित पेड़ तक पहुंच व्यापक रूप से बिखरी हुई है और अधिकतर यादृच्छिक है, और इसे समानांतर कलन विधि में बदलने का कोई सीधा तरीका नहीं है।

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

एक अच्छी तरह से कार्यान्वित क्विकसॉर्ट आमतौर पर हीपसॉर्ट की तुलना में 2-3 गुना तेज होता है। हालाँकि क्विकॉर्ट के लिए कम तुलनाओं की आवश्यकता होती है, यह एक मामूली कारक है। (दोगुने तुलनाओं का दावा करने वाले परिणाम टॉप-डाउन संस्करण को माप रहे हैं; देखें § Bottom-up heapsort.) क्विकसॉर्ट का मुख्य लाभ इसके संदर्भ का बेहतर स्थानीयता है: विभाजन अच्छे स्थानिक इलाके के साथ एक रैखिक स्कैन है, और पुनरावर्ती उपखंड में अच्छा अस्थायी इलाका है। अतिरिक्त प्रयास के साथ, क्विकॉर्ट को ज्यादातर शाखा-मुक्त कोड में भी लागू किया जा सकता है, और समानांतर में उप-विभाजन को सॉर्ट करने के लिए कई सीपीयू का उपयोग किया जा सकता है। इस प्रकार, जब अतिरिक्त प्रदर्शन कार्यान्वयन प्रयास को उचित ठहराता है तो क्विकॉर्ट को प्राथमिकता दी जाती है।

दूसरा प्रमुख 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

संदर्भ

• 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