हीप सॉर्ट बाइनरी हीप डेटा स्ट्रक्चर पर आधारित एक सॉर्टिंग तकनीक है। हीप सॉर्ट के साथ आगे बढ़ने के लिए, आपको बाइनरी ट्री और बाइनरी हीप से परिचित होना होगा।
कंप्लीट बाइनरी ट्री क्या है?
एक कंप्लीट बाइनरी ट्री एक ट्री डेटा स्ट्रक्चर है जहां लास्ट लेवल को छोड़कर सभी लेवल पूरी तरह भरे होते हैं। लास्ट लेवल को लेफ्ट साइड से भरा होना चाहिए।
बाइनरी हीप क्या है?
बाइनरी हीप बाइनरी ट्री का एक विशेष मामला है। बाइनरी हीप दो प्रकार के होते हैं -
मैक्स हीप - प्रत्येक लेवल पर पैरेंट नोड अपने चाइल्ड नोड्स से बड़ा होता है।
मिन हीप - प्रत्येक लेवल पर पैरेंट नोड अपने चाइल्ड नोड्स से छोटा होता है।
कंप्लीट बाइनरी ट्री का ऐरे रिप्रेजेंटेशन
बाइनरी हीप को ऐरे के रूप में दर्शाया जा सकता है क्योंकि यह स्पेस एफिशिएंट है। यदि पैरेंट नोड इंडेक्स 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)Python में हीप सॉर्ट का पूरा प्रोग्राम इस प्रकार है -
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 log n)
