हीप सॉर्ट बाइनरी हीप डेटा संरचना पर आधारित है। बाइनरी हीप में पैरेंट नोड के चाइल्ड नोड्स अधिकतम हीप के मामले में उससे छोटे या उसके बराबर होते हैं, और पैरेंट नोड के चाइल्ड नोड्स मिन हीप के मामले में उससे बड़े या उसके बराबर होते हैं।
हीप सॉर्ट में सभी चरणों की व्याख्या करने वाला एक उदाहरण इस प्रकार है।
छँटाई से पहले 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;
i nt i;
cout<<"Given array is: "<<endl;
for (i = 0; i *lt; n; i++)
cout<<arr[i]<<" ";
cout<<endl;
heapSort(arr, n);
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";
} आउटपुट
Given array is: 20 7 1 54 10 15 90 23 77 25 Sorted array is: 1 7 10 15 20 23 25 54 77 90
उपरोक्त कार्यक्रम में, फ़ंक्शन heapify () का उपयोग तत्वों को एक ढेर में बदलने के लिए किया जाता है। यह फ़ंक्शन एक पुनरावर्ती फ़ंक्शन है और यह उस तत्व से शुरू होने वाला अधिकतम ढेर बनाता है जिसे इस मामले में i.e. कहा जाता है। इसे प्रदर्शित करने वाला कोड स्निपेट निम्नानुसार दिया गया है।
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 () हीप सॉर्ट का उपयोग करके सरणी तत्वों को सॉर्ट करता है। यह नॉन-लीफ नोड्स से शुरू होता है और उनमें से प्रत्येक पर हीपिफाई () को कॉल करता है। यह सरणी को बाइनरी अधिकतम ढेर में परिवर्तित करता है। इसे इस प्रकार दिखाया गया है -
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);
} फ़ंक्शन मुख्य () में, पहले सरणी प्रदर्शित होती है। फिर, सरणी को सॉर्ट करने के लिए फ़ंक्शन heapSort() को कॉल किया जाता है। यह निम्नलिखित कोड स्निपेट द्वारा दिया गया है।
cout<<"Given array is: "<<endl; for (i = 0; i < n; i++) cout<<arr[i]<<" "; cout<<endl; heapSort(arr, n);
अंत में, क्रमबद्ध सरणी प्रदर्शित की जाती है। यह नीचे दिखाया गया है।
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";