हीप सॉर्ट बाइनरी हीप डेटा संरचना पर आधारित है। बाइनरी हीप में, मैक्स हीप के मामले में पैरेंट नोड के चाइल्ड नोड्स उससे छोटे या बराबर होते हैं, और मिन हीप के मामले में चाइल्ड नोड्स पैरेंट से बड़े या बराबर होते हैं।
हीप सॉर्ट के सभी चरणों को समझाने वाला एक उदाहरण निम्नलिखित है।
सॉर्टिंग से पहले 10 तत्वों की मूल सरणी इस प्रकार है:
| 20 | 7 | 1 | 54 | 10 | 15 | 90 | 23 | 77 | 25 |
इस सरणी को मैक्स-हीपिफाई का उपयोग करके बाइनरी मैक्स हीप में बनाया जाता है। सरणी के रूप में दर्शाया गया यह मैक्स हीप निम्नलिखित है:
| 90 | 77 | 20 | 54 | 25 | 15 | 1 | 23 | 7 | 10 |
मैक्स हीप के रूट एलिमेंट को निकालकर सरणी के अंत में रखा जाता है। फिर शेष एलिमेंट्स को मैक्स हीप में बदलने के लिए मैक्स हीपिफाई को कॉल किया जाता है। यह प्रक्रिया तब तक चलती है जब तक अंततः सॉर्ट की गई सरणी प्राप्त नहीं हो जाती, जो इस प्रकार है:
| 1 | 7 | 10 | 15 | 20 | 23 | 25 | 54 | 77 | 90 |
हीप सॉर्ट एल्गोरिदम का उपयोग करके 10 तत्वों की सरणी को सॉर्ट करने का प्रोग्राम निम्नलिखित है।
उदाहरण
#include<iostream> using namespace std; void heapify(int arr[], int n, int i) { int temp; int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; if (largest != i) { temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } void heapSort(int arr[], int n) { int temp; for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i = n - 1; i >= 0; i--) { temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } int main() { int arr[] = { 20, 7, 1, 54, 10, 15, 90, 23, 77, 25}; int n = 10; int i; cout<<"दी गई सरणी है: "<<endl; for (i = 0; i < n; i++) cout<<arr[i]<<" "; cout<<endl; heapSort(arr, n); printf("\nसॉर्ट की गई सरणी है: \n"); for (i = 0; i < n; ++i) cout<<arr[i]<<" "; } आउटपुट
दी गई सरणी है: 20 7 1 54 10 15 90 23 77 25 सॉर्ट की गई सरणी है: 1 7 10 15 20 23 25 54 77 90
उपरोक्त प्रोग्राम में, heapify() फ़ंक्शन का उपयोग एलिमेंट्स को हीप में बदलने के लिए किया जाता है। यह फ़ंक्शन एक रिकर्सिव फ़ंक्शन है और यह उस एलिमेंट से शुरू करके मैक्स हीप बनाता है जिस पर इसे कॉल किया जाता है, यानी इस मामले में i। इसे दर्शाने वाला कोड स्निपेट निम्नलिखित है।
void heapify(int arr[], int n, int i) { int temp; int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; if (largest != i) { temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } heapSort() फ़ंक्शन सरणी एलिमेंट्स को हीप सॉर्ट का उपयोग करके सॉर्ट करता है। यह नॉन-लीफ नोड्स से शुरू होता है और उनमें से प्रत्येक पर heapify() कॉल करता है। यह सरणी को बाइनरी मैक्स हीप में बदल देता है। यह निम्नलिखित कोड द्वारा दिखाया गया है:
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
इसके बाद, heapSort() फ़ंक्शन फॉर लूप के प्रत्येक पुनरावृत्ति में रूट एलिमेंट को लेता है और इसे सरणी के अंत में रखता है। फिर heapify() को यह सुनिश्चित करने के लिए कॉल किया जाता है कि शेष एलिमेंट्स मैक्स हीप हैं। अंततः, इस विधि का उपयोग करके सभी एलिमेंट्स को मैक्स हीप से निकाल लिया जाता है और एक सॉर्ट की गई सरणी प्राप्त होती है। यह निम्नलिखित कोड द्वारा दिखाया गया है।
for (int i = n - 1; i >= 0; i--) { temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } main() फ़ंक्शन में, पहले सरणी को प्रदर्शित किया जाता है। फिर, सरणी को सॉर्ट करने के लिए heapSort() फ़ंक्शन को कॉल किया जाता है। यह निम्नलिखित कोड स्निपेट द्वारा दिया गया है।
cout<<"दी गई सरणी है: "<<endl; for (i = 0; i < n; i++) cout<<arr[i]<<" "; cout<<endl; heapSort(arr, n);
अंत में, सॉर्ट की गई सरणी प्रदर्शित की जाती है। यह नीचे दिखाया गया है।
printf("\nसॉर्ट की गई सरणी है: \n"); for (i = 0; i < n; ++i) cout<<arr[i]<<" "; 
