Heap sort
“Heap Sort एकTime Complexity हर case में O(n log n) होती है। जो Binary Heap (Max Heap या Min Heap) data structure का उपयोग करके elements को ascending या descending order में sort करता है। इसमें सबसे पहले array को एक heap (Max Heap/Min Heap) में convert किया जाता है और फिर heap से बार-बार root element निकालकर final sorted order बनाया जाता है।”
Key Point :
- Heap Sort एक efficient in-place sorting algorithm है।
- यह Binary Heap (Max Heap/Min Heap) पर काम करता है।
- Ascending order sorting के लिए हमेशा Max Heap used होता है।
- Time Complexity हर case में O(n log n) होती है।
What is Heap? (Heap क्या होता है?)
Heap एक complete binary tree होता है जिसमें दो प्रकार के orders follow होते हैं :
1. Max Heap
- हर parent node हमेशा अपने children से बड़ा होता है।
- Root = सबसे बड़ा element।
2. Min Heap
- Parent हमेशा children से छोटा होता है।
- Root = सबसे छोटा element।
Heap Sort में ascending order के लिए हम Max Heap का उपयोग करते हैं।
Working of Heap Sort
Heap Sort का working दो मुख्य steps में पूरा होता है :
Step 1: Build Max Heap (पूरे array को Max Heap में बदलना)
- Ascending order sorting के लिए हमें largest element पहले चाहिए।
- Max Heap में root node हमेशा सबसे बड़ा होता है, इसलिए पहले array को Max Heap में convert किया जाता है।
Procedure :
- Last non-leaf node से start करते हैं।
- नीचे से ऊपर की तरफ heapify() apply करते हैं।
- पूरा binary tree Max Heap में convert हो जाता है।
Formula for Last Non-Leaf Node : last_non_leaf = (n / 2) – 1
Step 2: Heap Sort Process – Remove Max Element
Max Heap बन जाने के बाद actual sorting शुरू होती है:
- Root element (सबसे बड़ा element) को array के last element से swap करो।
- Heap size को 1 reduce करो (क्योंकि last position पर correct value आ चुकी है)।
- फिर से root पर heapify() apply करो।
- इस process को तब तक repeat करो जब तक heap size 1 न रह जाए।
हर step के बाद सबसे बड़े elements array के end में collect होते जाते हैं, जिससे array धीरे-धीरे sorted होता जाता है।
Meaning of Heapify (Heapify क्या है?)
Heapify वह process है जिसमें किसी भी subtree को Heap Property (Max Heap या Min Heap) follow करवाया जाता है।
Simple Explanation :
- Parent node को उसके left और right children से compare किया जाता है।
- यदि कोई child parent से बड़ा (Max Heap में) या छोटा (Min Heap में) हो, तो parent के साथ swap किया जाता है।
- Swap के बाद नीचे वाले level पर फिर से heapify() apply किया जाता है।
- यह process नीचे की तरफ चलता रहता है जब तक पूरा subtree proper heap न बन जाए।
Example
A = [20, 5, 15, 22, 40, 3]
Step 1: Build Max Heap
Converting array into Max Heap :
20
/ \
5 15
/ \ /
22 40 3
Heapify apply करने पर :
40
/ \
22 15
/ \ /
20 5 3
Step 2: Required Sorting Output
अब root को last element से swap करते हैं।
1st swap → 40 को last पर भेज दो
Remaining heapify → सबसे बड़ा element end में fix हो गया
Repeat until entire array sorted –
Final Sorted Array : [ 3, 5, 15, 20, 22, 40 ] (Ascending order)
Pseudo Code
MAX-HEAPIFY(A, i):
left = 2*i + 1
right = 2*i + 2
largest = i
if left < heap_size and A[left] > A[largest]:
largest = left
if right < heap_size and A[right] > A[largest]:
largest = right
if largest != i:
swap A[i] and A[largest]
MAX-HEAPIFY(A, largest)
Applications of Heap Sort
1. Priority Queue Implementation : Heap Sort का आधार structure ही Binary Heap होता है, इसलिए इसका सबसे common उपयोग priority queue बनाने में होता है।
- CPU scheduling
- OS task management
- Network packet prioritization
2. Selection Algorithms : Heap का use करके हम बहुत जल्दी Kth largest या Kth smallest element निकाल सकते हैं।
- Competitive programming
- Data analysis tools
3. Sorting Large Datasets : Heap Sort in-place और O(n log n) होने के कारण large files या logs को तेज़ी से sort करता है।
- Big data platforms
- Server-side data sorting
- Cloud systems
4. Real-Time Systems : जहाँ worst-case performance भी guaranteed होना चाहिए, वहाँ Heap Sort ideal है।
- Banking systems
- Telecom billing
- Airline reservation systems
- Railway (IRCTC) transaction sorting
5. Graph Algorithms : Priority queue की वजह से heap कई graph algorithms में indirectly इस्तेमाल होता है।
- Shortest path calculation
- Minimum spanning tree (Prim’s Algorithm)
Advantages of Heap Sort
1. Fixed Time Complexity – O(n log n)
- Heap Sort हर स्थिति में समान performance देता है — चाहे input sorted, reverse sorted या random हो।
2. In-Place Sorting Algorithm
- यह extra memory उपयोग नहीं करता (Space Complexity : O(1)), इसलिए बड़े datasets को efficiently handle करता है।
3. Not Input Dependent
- Quick Sort के विपरीत, input pattern का इस पर कोई असर नहीं होता।
- Performance हर case में consistent रहता है।
4. Good for Large Data Processing
- Heap structure naturally balanced होता है, जिससे यह बड़े data जैसे servers, logs, analytics systems में अच्छा काम करता है।
5. Useful for Priority Queue Implementation
- Heap Sort का core concept priority queue में directly उपयोग किया जाता है— जैसे: OS scheduling, networking, graph algorithms आदि में।
6. Consistent and Reliable Performance
- Worst-case में भी performance degrade नहीं होती, इसलिए real-time systems में यह preferred choice है।
Disadvantages of Heap Sort
1. Not a Stable Sort
- Equal elements की ordering बदल सकती है, इसलिए stability-required applications के लिए सही नहीं है।
2. More Complex Algorithm
- Tree structure, heapify operations और swaps के कारण beginners को यह थोड़ा कठिन लगता है।
3. Slow on Small Data
- Small datasets पर Quick Sort और Merge Sort इससे तेज perform करते हैं।
4. Poor Cache Performance
- Heap में random memory access होता है, जिससे CPU cache properly utilize नहीं हो पाती।
5. Repeated Heapify Overhead
- हर pass में heapify call करनी पड़ती है, जिससे algorithm थोड़ा heavy लगता है और processing time बढ़ सकता है।
