इस ट्यूटोरियल में, आप सीखेंगे कि ढेर एल्गोरिथ्म कैसे काम करता है। इसके अलावा, आपको C, C ++, Java और पायथन में ढेर प्रकार के काम के उदाहरण मिलेंगे।
कंप्यूटर प्रोग्रामिंग में हीप सॉर्ट एक लोकप्रिय और कुशल सॉर्टिंग एल्गोरिथ्म है। ढेर सॉर्ट एल्गोरिथ्म को कैसे लिखना है, यह सीखना दो प्रकार के डेटा संरचनाओं के ज्ञान की आवश्यकता है - सरणियाँ और पेड़।
संख्याओं का प्रारंभिक सेट जिसे हम सॉर्ट करना चाहते हैं, एक सरणी में संग्रहीत किया जाता है उदा (10, 3, 76, 34, 23, 32)और सॉर्ट करने के बाद, हमें एक सॉर्ट किया गया सरणी मिलता है(3,10,23,32,34,76)
हीप क्रम सरणी के तत्वों को एक विशेष प्रकार के पूर्ण द्विआधारी वृक्ष के रूप में कल्पना करके काम करता है जिसे ढेर कहा जाता है।
एक शर्त के रूप में, आपको एक पूर्ण बाइनरी ट्री और हीप डेटा संरचना के बारे में पता होना चाहिए।
एरे इंडेक्स और ट्री तत्वों के बीच संबंध
एक पूर्ण बाइनरी ट्री में एक दिलचस्प संपत्ति है जिसका उपयोग हम किसी भी नोड के बच्चों और माता-पिता को खोजने के लिए कर सकते हैं।
यदि एरे में किसी तत्व का इंडेक्स i है, तो इंडेक्स 2i+1का तत्व लेफ्ट चाइल्ड बन जाएगा और 2i+2इंडेक्स में एलिमेंट सही बच्चा बन जाएगा। इसके अलावा, सूचकांक I पर किसी भी तत्व का मूल निम्न के द्वारा दिया गया है (i-1)/2।
सरणी और ढेर सूचकांकों के बीच संबंध
आइए इसका परीक्षण करें,
बाएं बच्चे का 1 (सूचकांक 0) = तत्व (2 * 0 + 1) सूचकांक = तत्व 1 सूचकांक में = 12 सही बच्चे का 1 = तत्व में (2 * 0 + 2) सूचकांक = तत्व 2 सूचकांक = 9 में इसी प्रकार 12 के बाएं बच्चे (इंडेक्स 1) = एलीमेंट इन (2 * 1 + 1) इंडेक्स = 3 इंडेक्स में तत्व = 5 12 का सही बच्चा = तत्व (2 * 1 + 2) इंडेक्स = तत्व 4 इंडेक्स = 6 में
आइए हम यह भी पुष्टि करें कि नियम किसी भी नोड के माता-पिता को खोजने के लिए हैं
9 (स्थिति 2) का जनक = (2-1) / 2 = 0.5 = 0.5 ~ 0 सूचकांक = 1 12 का अभिभावक (स्थिति 1) = (1-1) / 2 = 0 सूचकांक = 1
ट्री पोजिशन में एरे इंडेक्स की इस मैपिंग को समझना यह समझने के लिए महत्वपूर्ण है कि हीप डेटा स्ट्रक्चर कैसे काम करता है और इसका उपयोग हीप सॉर्ट को लागू करने के लिए कैसे किया जाता है।
हीप डाटा स्ट्रक्चर क्या है?
हीप एक विशेष वृक्ष-आधारित डेटा संरचना है। एक बाइनरी ट्री कहा जाता है कि यदि ढेर डेटा संरचना का पालन करना है
- यह एक पूर्ण बाइनरी ट्री है
- पेड़ के सभी नोड्स संपत्ति का पालन करते हैं कि वे अपने बच्चों की तुलना में अधिक हैं अर्थात सबसे बड़ा तत्व जड़ में है और इसके दोनों बच्चे और जड़ से छोटे और इतने पर। इस तरह के ढेर को अधिकतम-ढेर कहा जाता है। यदि इसके बजाय, सभी नोड्स अपने बच्चों की तुलना में छोटे हैं, तो इसे मिन-हीप कहा जाता है
निम्न उदाहरण आरेख मैक्स-हीप और मिन-हीप दिखाता है।
मैक्स हीप और मिन हीप
इसके बारे में अधिक जानने के लिए, कृपया Heap Data Structure पर जाएँ।
एक पेड़ को "ढेर" कैसे करें
पूर्ण बाइनरी ट्री से शुरू करके, हम इसे ढेर के सभी गैर-पत्ती तत्वों पर heapify नामक एक फ़ंक्शन चलाकर मैक्स-हीप बनने के लिए संशोधित कर सकते हैं।
चूँकि heapify पुनरावर्तन का उपयोग करता है, इसलिए इसे समझ पाना मुश्किल हो सकता है। तो चलिए पहले विचार करते हैं कि आप केवल तीन तत्वों के साथ एक पेड़ को कैसे ढेर करेंगे।
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
आधार मामलों को सुरक्षित करें
ऊपर दिया गया उदाहरण दो परिदृश्य दिखाता है - एक जिसमें रूट सबसे बड़ा तत्व है और हमें कुछ भी करने की आवश्यकता नहीं है। और एक और जिसमें जड़ में एक बच्चे के रूप में एक बड़ा तत्व था और हमें अधिकतम-ढेर संपत्ति बनाए रखने के लिए स्वैप करने की आवश्यकता थी।
यदि आपने पहले पुनरावर्ती एल्गोरिदम के साथ काम किया है, तो संभवतः आपने पहचान लिया है कि यह आधार मामला होना चाहिए।
अब आइए एक और परिदृश्य पर विचार करें जिसमें एक से अधिक स्तर हैं।
जड़ तत्व को कैसे ढेर किया जाए जब इसके उपप्रकार पहले से ही अधिकतम ढेर हों
शीर्ष तत्व अधिकतम-ढेर नहीं है, लेकिन सभी उप-पेड़ अधिकतम-ढेर हैं।
पूरे पेड़ के लिए अधिकतम-ढेर संपत्ति को बनाए रखने के लिए, हमें 2 नीचे की ओर धकेलना होगा जब तक कि वह अपनी सही स्थिति तक नहीं पहुंच जाता।
जड़ तत्व को कैसे समाहित किया जाए, जब इसके उपप्रकार अधिकतम-ढेर हों
इस प्रकार, एक पेड़ में अधिकतम-ढेर संपत्ति को बनाए रखने के लिए, जहां दोनों उप-पेड़ अधिकतम-ढेर हैं, हमें रूट तत्व पर बार-बार ढेर करने की आवश्यकता है जब तक कि वह अपने बच्चों से बड़ा न हो या यह पत्ती का नोड बन जाए।
हम इन दोनों स्थितियों को एक हीपेय फ़ंक्शन में जोड़ सकते हैं
void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) )
यह फ़ंक्शन आधार मामले और किसी भी आकार के पेड़ के लिए दोनों काम करता है। इस प्रकार हम रूट तत्व को किसी भी पेड़ के आकार के लिए अधिकतम-हीप स्थिति बनाए रखने के लिए सही स्थिति में ले जा सकते हैं जब तक कि उप-पेड़ अधिकतम-ढेर हैं।
अधिकतम-ढेर बनाएँ
किसी भी पेड़ से अधिकतम ढेर का निर्माण करने के लिए, हम इस प्रकार नीचे के ऊपर से प्रत्येक उप-पेड़ को ढेर करना शुरू कर सकते हैं और जड़ तत्व सहित सभी तत्वों को फ़ंक्शन के लागू होने के बाद अधिकतम-ढेर के साथ समाप्त कर सकते हैं।
एक पूर्ण पेड़ के मामले में, एक गैर-पत्ती नोड का पहला सूचकांक द्वारा दिया जाता है n/2 - 1। उसके बाद के अन्य सभी नोड्स लीफ-नोड्स हैं और इस प्रकार उन्हें सुरक्षित करने की आवश्यकता नहीं है।
तो, हम अधिकतम हीप का निर्माण कर सकते हैं
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
सरणी बनाएं और 
ढेर चरणों के लिए अधिकतम हीप बनाने के लिए i स्टेप्स की गणना करें। हीप सॉर्ट 
के लिए अधिकतम हीप बनाने के लिए 
चरण। हीप सॉर्ट के लिए अधिकतम हीप बनाने के लिए चरण
जैसा कि ऊपर चित्र में दिखाया गया है, हम सबसे छोटे पेड़ों को काटते हुए शुरू करते हैं और धीरे-धीरे ऊपर जाते हैं जब तक कि हम जड़ तत्व तक नहीं पहुंच जाते।
यदि आप यहाँ तक सब कुछ समझ चुके हैं, बधाई हो, तो आप हीप क्रम में महारत हासिल करने की राह पर हैं।
कैसे ढेर काम करता है?
- चूंकि पेड़ मैक्स-हीप संपत्ति को संतुष्ट करता है, तो सबसे बड़ा आइटम रूट नोड पर संग्रहीत किया जाता है।
- स्वैप: मूल तत्व को हटा दें और सरणी के अंत में डाल दें (nth स्थिति) रिक्त स्थान पर पेड़ (ढेर) का अंतिम आइटम रखें।
- निकालें: 1 से ढेर के आकार को कम करें।
- Heapify: रूट एलिमेंट को फिर से करें ताकि हमारे पास रूट में उच्चतम तत्व हो।
- प्रक्रिया को दोहराया जाता है जब तक कि सूची के सभी आइटम सॉर्ट नहीं किए जाते हैं।
स्वैप, निकालें और Heapify करें
नीचे दिया गया कोड ऑपरेशन दिखाता है।
// Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); )
पायथन, जावा और सी / सी ++ उदाहरण
पायथन जावा सी सी ++ # Heap Sort in 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("%d " % arr(i), end='')
// Heap Sort in Java public class HeapSort ( public void sort(int arr()) ( int n = arr.length; // Build max heap for (int i = n / 2 - 1; i>= 0; i--) ( heapify(arr, n, i); ) // Heap sort for (int i = n - 1; i>= 0; i--) ( int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // Heapify root element heapify(arr, i, 0); ) ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l arr(largest)) largest = l; if (r arr(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int swap = arr(i); arr(i) = arr(largest); arr(largest) = swap; heapify(arr, n, largest); ) ) // Function to print an array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver code public static void main(String args()) ( int arr() = ( 1, 12, 9, 5, 6, 10 ); HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); ) )
// Heap Sort in C #include // Function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) ) // Main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) printf("%d ", arr(i)); printf(""); ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); printf("Sorted array is "); printArray(arr, n); )
// Heap Sort in C++ #include using namespace std; void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(arr(i), arr(largest)); heapify(arr, n, largest); ) ) // main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(arr(0), arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) cout << arr(i) << " "; cout << ""; ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); cout << "Sorted array is "; printArray(arr, n); )
ढेर क्रमबद्धता
हीप सॉर्ट में O(nlog n)सभी मामलों के लिए समय जटिलताएं हैं (सबसे अच्छा मामला, औसत मामला और सबसे खराब मामला)।
आइए हम इसका कारण समझें। एन तत्वों से युक्त एक पूर्ण बाइनरी ट्री की ऊंचाई हैlog n
As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.
In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.
Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.
Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.
Heap Sort Applications
Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort's running time and constant O(1) upper bound on its auxiliary storage.
हालाँकि, हीप सॉर्ट में O(n log n)सबसे खराब स्थिति के लिए भी समय की जटिलता है, लेकिन इसमें अधिक एप्लिकेशन (क्विक सॉर्ट, मर्ज सॉर्ट जैसे अन्य सॉर्टिंग एल्गोरिदम की तुलना में) नहीं है। हालाँकि, इसकी अंतर्निहित डेटा संरचना, हीप को कुशलतापूर्वक उपयोग किया जा सकता है, यदि हम छांटे गए क्रम में शेष वस्तुओं को रखने के बिना वस्तुओं की सूची से सबसे छोटी (या सबसे बड़ी) निकालना चाहते हैं। उदाहरण के लिए प्राथमिकता कतार।
