हीप सॉर्ट एल्गोरिथ्म (कोड के साथ) Python और C++)
सारा चेन
हीप सॉर्ट एल्गोरिथ्म क्या है?
हीप सॉर्ट लोकप्रिय और तेज़ सॉर्टिंग एल्गोरिदम में से एक है। यह पूर्ण बाइनरी ट्री डेटा संरचना पर बनाया गया है। हम अधिकतम तत्व की खोज करेंगे और इसे अधिकतम हीप के लिए शीर्ष पर रखेंगे। हम इसे बाइनरी ट्री के पैरेंट नोड पर रखेंगे।
मान लीजिए एक सारणी दी गई है, डेटा = [10,5, 7, 9, 4, 11, 45, 17, 60].
सरणी में, यदि i-th (i=0,1,2,3 …) इंडेक्स पैरेंट नोड है, तो (2i+1) और (2i+2) बाएं और दाएं बच्चे होंगे। इस सरणी के साथ एक पूर्ण बाइनरी ट्री बनाना इस तरह दिखेगा:
हम सरणी के आरंभ से अंत तक हीपिफ़ाई प्रक्रिया करेंगे। शुरू में, अगर हम सरणी को एक पेड़ में बदल देते हैं, तो यह ऊपर दिए गए जैसा दिखाई देगा। हम देख सकते हैं कि यह कोई हीप प्रॉपर्टी (मिन-हीप या मैक्स हीप) बनाए नहीं रख रहा है। हम सभी नोड्स के लिए हीपिफ़ाई प्रक्रिया करके सॉर्टेड सरणी प्राप्त करेंगे।
हीप सॉर्ट का अनुप्रयोग
यहाँ हीप सॉर्ट एल्गोरिथ्म का कुछ उपयोग दिया गया है:
- "प्राथमिकता कतारों" के निर्माण के लिए हीप सॉर्ट की आवश्यकता होती है। क्योंकि हीपसॉर्ट प्रत्येक प्रविष्टि के बाद तत्व को सॉर्ट रखता है।
- हीप डेटा संरचना k खोजने में कुशल हैth किसी दिए गए सारणी में सबसे बड़ा तत्व.
- लिनक्स कर्नेल डिफ़ॉल्ट रूप से हीप सॉर्ट का उपयोग करता है छँटाई एल्गोरिथ्म क्योंकि इसमें O (1) स्थान जटिलता है।
उदाहरण के साथ हीप सॉर्ट बनाएं
यहां, हम निम्नलिखित पूर्ण बाइनरी ट्री से एक अधिकतम हीप का निर्माण करेंगे।
लीफ नोड्स 17, 60, 4, 11 और 45 हैं। उनके पास कोई चाइल्ड नोड नहीं है। इसलिए वे लीफ नोड्स हैं। इसलिए, हम उनके पैरेंट नोड से हीपिफ़ाई विधि शुरू करेंगे। यहाँ चरण दिए गए हैं:
चरण 1) सबसे बाएं उप-वृक्ष का चयन करें। यदि चाइल्ड नोड अधिक हैं, तो पैरेंट नोड को चाइल्ड नोड से बदलें।
यहाँ पैरेंट नोड 9 है। और चाइल्ड नोड 17 और 60 हैं। चूंकि 60 सबसे बड़ा है, इसलिए 60 और 9 को आपस में बदल दिया जाएगा। अधिकतम ढेर.
चरण 2) अब, सबसे बाईं ओर का सबट्री हीपिफ़ाइड है। अगला पैरेंट नोड 7 है। इस पैरेंट के दो चाइल्ड नोड हैं, और सबसे बड़ा 45 है। इसलिए, 45 और 7 को स्वैप किया जाएगा।
चरण 3) नोड्स 60 और 4 में पैरेंट नोड 5 है। चूंकि "5" चाइल्ड नोड 60 से छोटा है, इसलिए इसे स्वैप किया जाएगा।
चरण 4) अब, नोड 5 में चाइल्ड नोड 17,9 है। यह अधिकतम हीप प्रॉपर्टी को बनाए नहीं रख रहा है। इसलिए, 5 को 17 से बदल दिया जाएगा।
चरण 5) नोड 10 को 60 के साथ बदला जाएगा, फिर 17 के साथ बदला जाएगा। प्रक्रिया निम्नलिखित की तरह दिखाई देगी।
चरण 6) चरण 5 तक, हमने अधिकतम हीप बनाया। प्रत्येक पैरेंट नोड अपने चाइल्ड नोड से बड़ा होता है। रूट नोड का अधिकतम मान (60) होता है।
नोट: क्रमबद्ध सरणी बनाने के लिए, हमें अधिकतम मूल्य वाले नोड को उसके उत्तराधिकारी के साथ प्रतिस्थापित करना होगा।
इस प्रक्रिया को "अधिकतम निकालें". चूंकि 60 अधिकतम नोड है, हम इसकी स्थिति को 0वें इंडेक्स पर तय करेंगे और नोड 60 के बिना हीप बनाएंगे।
चरण 7) जैसे ही 60 हटा दिया जाता है, तो अगला अधिकतम मान 45 है। हम नोड 45 से फिर से “Extract Max” प्रक्रिया करेंगे।
इस बार हम 45 प्राप्त करेंगे और मूल नोड को उसके उत्तराधिकारी 17 से प्रतिस्थापित करेंगे।
हमें प्रदर्शन करने की आवश्यकता है "अधिकतम निकालें” जब तक सभी तत्व क्रमबद्ध न हो जाएं।
इन चरणों को करने के बाद जब तक हम सभी अधिकतम मानों को निकाल नहीं लेते, हमें निम्नलिखित सारणी प्राप्त होगी।
बाइनरी हीप क्या है?
बाइनरी हीप एक तरह का पूर्ण है बाइनरी वृक्ष डेटा संरचना। इस तरह की ट्री संरचना में, पैरेंट नोड चाइल्ड नोड्स से बड़ा या छोटा होता है। यदि पैरेंट नोड छोटा है, तो हीप को "मिनिमल हीप" कहा जाता है और यदि पैरेंट नोड बड़ा है, तो हीप को "मैक्स हीप" कहा जाता है।
यहां न्यूनतम हीप और अधिकतम हीप के उदाहरण दिए गए हैं।
ऊपर दिए गए चित्र में, यदि आप "मिनिमल हीप" पर ध्यान दें, तो पैरेंट नोड हमेशा अपने चाइल्ड नोड से छोटा होता है। पेड़ के शीर्ष पर, हम सबसे छोटा मान 10 पा सकते हैं।
इसी तरह, "मैक्स हीप" के लिए, पैरेंट नोड हमेशा चाइल्ड नोड से बड़ा होता है। "मैक्स हीप" के लिए अधिकतम तत्व हेड नोड पर मौजूद होता है।
“हीपफाई” क्या है?
"हीपिफ़ाई" हीप का सिद्धांत है जो नोड की स्थिति सुनिश्चित करता है। हीपिफ़ाई में, अधिकतम हीप हमेशा पैरेंट और चाइल्ड के साथ संबंध बनाए रखता है, और यानी पैरेंट नोड चाइल्ड नोड्स से बड़ा होगा।
उदाहरण के लिए, यदि कोई नया नोड जोड़ा जाता है, तो हमें हीप को फिर से आकार देने की आवश्यकता होती है। हालाँकि, हमें नोड्स को बदलने या स्वैप करने या सरणी को पुनर्व्यवस्थित करने की आवश्यकता हो सकती है। हीप को फिर से आकार देने की इस प्रक्रिया को "हीपिफ़ाई" कहा जाता है।
यहाँ एक उदाहरण दिया गया है कि हीपफाई कैसे काम करता है:
हीपफाई के लिए चरण इस प्रकार हैं:
चरण 1) नोड 65 के दाएं बच्चे के रूप में नोड 60 को जोड़ा गया।
चरण 2) जाँच करें कि क्या नया जोड़ा गया नोड पैरेंट नोड से बड़ा है।
चरण 3) चूंकि यह मूल नोड से बड़ा है, इसलिए हमने दाएं चाइल्ड नोड को उसके मूल नोड से बदल दिया।
हीप का निर्माण कैसे करें
हीप बनाने या ट्री को हीपफाई करने से पहले, हमें यह जानना होगा कि हम इसे कैसे स्टोर करेंगे। चूंकि हीप एक पूर्ण बाइनरी ट्री है, इसलिए इसका उपयोग करना बेहतर है सरणी ढेर का डेटा रखने के लिए.
मान लीजिए कि एक सरणी में कुल n तत्व हैं। यदि “i”वां इंडेक्स पैरेंट नोड है, तो बायां नोड इंडेक्स पर होगा (2i+1), और दायाँ नोड इंडेक्स पर होगा (2i+2)हम मान रहे हैं कि सरणी सूचकांक 0 से शुरू होता है।
इसका उपयोग करते हुए, आइए एक अधिकतम हीप को एक सरणी-जैसे निम्नांकित रूप में संग्रहीत करें:
हीपिफ़ाई एल्गोरिथ्म हीप प्रॉपर्टी को बनाए रखता है। यदि पैरेंट में चरम मान (छोटा या बड़ा) नहीं है, तो इसे सबसे चरम चाइल्ड नोड के साथ स्वैप किया जाएगा।
अधिकतम हीप को हीपीकृत करने के लिए निम्न चरण दिए गए हैं:
चरण 1) पत्ती नोड से शुरू करें.
चरण 2) माता-पिता और बच्चों के बीच अधिकतम ज्ञात करें।
चरण 3) यदि चाइल्ड नोड का मान पैरेंट नोड से बड़ा है तो नोड्स को स्वैप करें।
चरण 4) एक स्तर ऊपर जाओ.
चरण 5) जब तक हम सूचकांक 2,3,4 तक नहीं पहुंच जाते या संपूर्ण वृक्ष को क्रमबद्ध नहीं कर लेते, तब तक चरण 0 का पालन करें।
पुनरावर्ती हीपफाई (अधिकतम हीप) के लिए छद्म कोड इस प्रकार है:
def heapify(): input→ array, size, i largest = i left = 2*i + 1 right = 2*i + 2 if left<n and array[largest ] < array[left]: largest = left if right<n and array[largest ] < array[right]: largest = right If largest not equals i: swap(array[i],array[largest]) heapify(array,n,largest)
हीप सॉर्ट के लिए छद्म कोड
यहाँ हीप सॉर्ट एल्गोरिथ्म के लिए छद्म कोड दिया गया है:
Heapify(numbers as an array, n as integer, i as integer): largest = i left = 2i+1 right= 2i+2 if(left<=n) and (numbers[i]<numbers[left]) largest=left if(right<=n) and (numbers[i]<numbers[right]) largest=right if(largest != i) swap(numbers[i], numbers[largest]) Heapify(numbers,n,largest) HeapSort(numbers as an array): n= numbers.size() for i in range n/2 to 1 Heapify(numbers,n,i) for i in range n to 2 Swap numbers[i] with numbers[1] Heapify(numbers,i,0)
हीप सॉर्ट कोड का उदाहरण C++
#include <iostream>
using namespace std;
void display(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
}
void heapify(int numbers[], int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && numbers[left] < numbers[largest])
{
largest = left;
}
if (right < n && numbers[right] < numbers[largest])
{
largest = right;
}
if (largest != i)
{
//uncomment the following line to see details in output
//cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
swap(numbers[i], numbers[largest]);
heapify(numbers, n, largest);
}
}
void heapSort(int numbers[], int n)
{
for (int i = n/2 - 1; i >= 0; i--)
{
heapify(numbers, n, i);
//uncomment the following line to see details in output
//cout<<"Heapify:\t";
//display(numbers,n);
}
for (int i = n - 1; i >= 0; i--)
{
swap(numbers[0], numbers[i]);
heapify(numbers, i, 0);
}
}
int main()
{
int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
int size = sizeof(numbers) / sizeof(numbers[0]);
cout<<"Initial Array:\t";
display(numbers,size);
heapSort(numbers, size);
cout<<"Sorted Array (descending order):\t";
display(numbers, size);
}
आउटपुट:
Initial Array: 10 5 7 9 4 11 45 17 60 Sorted Array (descending order): 60 45 17 11 10 9 7 5 4
हीप सॉर्ट कोड का उदाहरण Python
def display(arr):
for i in range(len(arr)):
print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
largest = left
if right < n and numbers[right] < numbers[largest]:
largest = right
if largest != i:
numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
for i in range(n //2,-1,-1):
heapify(items, n, i) for i in range(n - 1, -1, -1):
items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)
आउटपुट:
Initial List: 10 5 7 9 4 11 45 17 60 After HeapSort: 60 45 17 11 10 9 7 5 4
हीप सॉर्ट का समय और स्थान जटिलता विश्लेषण
समय जटिलता और स्थान जटिलता है जिसका हम हीप सॉर्ट के लिए विश्लेषण कर सकते हैं। समय जटिलता के लिए हमारे पास निम्नलिखित मामले हैं:
- सबसे अच्छा मामला
- औसत मामला
- सबसे खराब मामला
हीप को एक पूर्ण बाइनरी ट्री पर लागू किया जाता है। इसलिए, बाइनरी ट्री के निचले स्तर पर, नोड्स की अधिकतम संख्या होगी। यदि निचले स्तर पर n नोड्स हैं, तो ऊपर के स्तर पर n/2 नोड्स होंगे।
इस उदाहरण में, लेवल 3 में चार आइटम हैं, लेवल 2 में दो आइटम हैं, और लेवल 1 में एक आइटम है। यदि आइटम की कुल संख्या n है, तो ऊंचाई या कुल स्तर होगा लॉग इन2(एन)। इसलिए, एक एकल तत्व को सम्मिलित करने में अधिकतम Log(n) पुनरावृत्तियाँ लग सकती हैं।
जब हम हीप से अधिकतम मान लेना चाहते हैं, तो हम बस रूट नोड लेते हैं। फिर, फिर से हीपिफ़ाई चलाएँ। प्रत्येक हीपिफ़ाई लेता है लॉग इन2(एन) समय. अधिकतम निकालने में O(1) समय लगता है.
हीप सॉर्ट एल्गोरिथ्म के लिए सर्वोत्तम केस समय जटिलता
जब सभी तत्व पहले से ही सरणी में क्रमबद्ध हैं, तो हीप बनाने में O(n) समय लगेगा। क्योंकि अगर सूची क्रमबद्ध है तो आइटम डालने में स्थिर समय लगेगा जो O(1) है।
इसलिए, सर्वोत्तम स्थिति में अधिकतम-हीप या न्यूनतम-हीप बनाने में O(n) समय लगेगा।
हीप सॉर्ट एल्गोरिथ्म के लिए औसत केस समय जटिलता
किसी आइटम को सम्मिलित करने या अधिकतम निकालने में O(log(n)) समय लगता है। इसलिए, हीप सॉर्ट एल्गोरिथ्म के लिए औसत केस समय जटिलता है ओ(एन लॉग(एन)).
हीप सॉर्ट एल्गोरिथ्म के लिए सबसे खराब स्थिति समय जटिलता
औसत मामले की तरह, सबसे खराब स्थिति में, हमें n बार हीपिफ़ाई करना पड़ सकता है। प्रत्येक हीपिफ़ाई में O(log(n)) समय लगेगा। इसलिए, सबसे खराब स्थिति में समय जटिलता होगी ओ(एन लॉग(एन)).
हीप सॉर्ट एल्गोरिथ्म के लिए स्थान जटिलता
हीप सॉर्ट एक इन-प्लेस डिज़ाइन किया गया एल्गोरिथम है। इसका मतलब है कि कार्य करने के लिए किसी अतिरिक्त या अस्थायी मेमोरी की आवश्यकता नहीं है। यदि हम कार्यान्वयन को देखें, तो हम देखेंगे कि हमने नोड्स के आदान-प्रदान के लिए स्वैप () का उपयोग किया है। किसी अन्य सूची या सरणी की आवश्यकता नहीं थी। इसलिए, स्पेस जटिलता O(1) है।
