पायथन में हीप सॉर्ट क्या है?

हीप सॉर्ट बाइनरी हीप डेटा संरचना पर आधारित छँटाई तकनीक है। हीप सॉर्ट के साथ आगे बढ़ने के लिए, आपको बाइनरी ट्री और बाइनरी हीप से परिचित होना चाहिए।

पूर्ण बाइनरी ट्री क्या है?

एक पूर्ण बाइनरी ट्री एक ट्री डेटा संरचना है जहां अंतिम को छोड़कर सभी स्तर पूरी तरह से भरे हुए हैं। अंतिम स्तर बाईं ओर से भरा जाना चाहिए।

बाइनरी हीप क्या है?

बाइनरी हीप बाइनरी ट्री का एक विशेष मामला है। बाइनरी हीप दो प्रकार के होते हैं -

• मैक्स हीप - प्रत्येक स्तर पर पैरेंट नोड उसके चाइल्ड नोड्स से बड़ा होता है।

• मिन हीप - प्रत्येक स्तर पर पैरेंट नोड उसके चाइल्ड नोड्स से छोटा होता है।

पूर्ण बाइनरी ट्री का सरणी प्रतिनिधित्व

बाइनरी हीप को एक सरणी के रूप में दर्शाया जा सकता है क्योंकि यह अंतरिक्ष कुशल है। अगर पैरेंट नोड को इंडेक्स I पर स्टोर किया जाता है, तो बाएं बच्चे की गणना 2 * i + 1 और दाएं बच्चे की 2 *i + 2 से की जा सकती है। मान लीजिए, इंडेक्स 0 से शुरू होता है।

हीप सॉर्ट एल्गोरिथम

• एक पूर्ण बाइनरी ट्री से अधिकतम ढेर बनाएं।

• रूट निकालें और इसे हीप में अंतिम तत्व से बदलें, हीप के आकार को 1 से कम करें और शेष नोड्स से फिर से अधिकतम हीप बनाएं।

• चरण 2 दोहराएं जब तक कि हमारे पास केवल 1 नोड शेष न हो।

एक पूर्ण बाइनरी ट्री से अधिकतम ढेर बनाएं

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

निम्नलिखित कोड एक पूर्ण बाइनरी ट्री से अधिकतम ढेर बनाता है जो मूल रूप से वह सरणी है जिसे हम सॉर्ट करना चाहते हैं।

def heapify(arr, n, i):
   # Find largest among root and children
   largest = i
   l = 2 * i + 1
   r = 2 * i + 2
   if l < n and arr[i] < arr[l]:
      largest = l
   if r < n and arr[largest] < arr[r]:
      largest = r
   # If root is not largest, swap with largest and continue heapifying
   if largest != i:
      arr[i], arr[largest] = arr[largest], arr[i]
      heapify(arr, n, largest)

हीप सॉर्ट

इस समय, हमारे पास अधिकतम ढेर है। अब हमें निम्नलिखित चीजें करने की जरूरत है।

• ढेर में अंतिम तत्व के साथ जड़ को स्वैप करें।

• ढेर के आकार को 1 से कम करें। (इसका मतलब है कि सबसे बड़ा तत्व अंतिम स्थान पर पहुंच गया है, हमें उस तत्व को ध्यान में रखने की आवश्यकता नहीं है)।

• अंतिम तत्व को छोड़कर अधिकतम ढेर का पुनर्निर्माण करें।

• उपरोक्त चरणों को तब तक दोहराएं जब तक हमारे पास केवल 1 तत्व शेष न हो।

for i in range(n-1, 0, -1):
   # Swap
   arr[i], arr[0] = arr[0], arr[i]

   # Heapify root element
   heapify(arr, i, 0)

पायथन में हीप सॉर्ट का पूरा कार्यक्रम इस प्रकार है -

def heapify(arr, n, i):
   # Find largest among root and children
   largest = i
   l = 2 * i + 1
   r = 2 * i + 2
   if l < n and arr[i] < arr[l]:
      largest = l
   if r < n and arr[largest] < arr[r]:
      largest = r
   # If root is not largest, swap with largest and continue heapifying
   if largest != i:
      arr[i], arr[largest] = arr[largest], arr[i]
      heapify(arr, n, largest)

def heapSort(arr):
   n = len(arr)
   # Build max heap
   for i in range(n//2, -1, -1):
      heapify(arr, n, i)
   for i in range(n-1, 0, -1):
      # Swap
      arr[i], arr[0] = arr[0], arr[i]
      # Heapify root element
      heapify(arr, i, 0)

arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
   print(arr[i], end=' ')

समय की जटिलता - O(n logn)