Heap Data Structure (हीप डाटा संरचना)
Heap एक specialized tree-based data structure है, जिसका मुख्य उद्देश्य efficiently maximum या minimum element तक पहुंचाना होता है। Heap एक complete binary tree होता है, और इसमें parent-child relationship एक predefined order के अनुसार maintain होती है।Heap को Priority Queue implement करने के लिए भी extensively use किया जाता है।
Uses : priority queue, CPU scheduling, graph algorithms, और real-time data streaming।
Examples :
- IRCTC में ticket booking के दौरान waiting list manage करना।
- CPU में high-priority tasks को schedule करना।
Heap को मुख्य रूप से दो types में divide किया जाता है : Max Heap और Min Heap। इसके अलावा advanced types भी हैं, जैसे Binomial Heap और Fibonacci Heap।
Types of Heap (प्रकार)
Heap मुख्यतः तीन types के होते हैं :
- Binary Heap
- Binomial Heap
- Fibonacci Heap
1. Binary Heap
Binary Heap सबसे common और popular type है। यह एक complete binary tree होता है। Binary Heap दो प्रकार के होते हैं :
a) Max Heap
- Parent node की value हमेशा children node से बड़ी होती है।
- Root node में maximum value रहती है।
- Use Case : Priority Queue, Job Scheduling, CPU Task Management
उदाहरण :
100
/ \
50 30
/ \ /
20 10 5
यहाँ root node में 100 है, जो सबसे बड़ी value है।
b) Min Heap
- Parent node की value हमेशा children node से छोटी होती है।
- Root node में minimum value रहती है।
Example :
5
/ \
10 20
/ \ /
50 30 100
2. Binomial Heap
Binomial Heap, binomial trees का एक collection होता है। इसमें merge, insert, delete, और find minimum operations बहुत efficiently perform किए जा सकते हैं। Binomial Heap का सबसे बड़ा advantage यह है कि, यह merging operations में बहुत fast होता है।
Use Cases : Graph algorithms जैसे – Dijkstra’s Shortest Path, Task scheduling
3. Fibonacci Heap
Fibonacci Heap एक advanced type heap है। इसमें decrease-key और merge operations बहुत fast होते हैं। इसका structure tree list के रूप में होता है, और amortized time complexity बहुत कम होती है, जिससे यह large-scale computations के लिए ideal है।
- Amortized time complexity एक तरीका है किसी algorithm या data structure की average time per operation को analyze करने का, जब हम operations की एक sequence perform करते हैं।
Use Cases : Graph algorithms, Network routing, Dynamic Programming optimization
Features of Heap (विशेषताएं)
1. Complete Binary Tree Structure
- Heap हमेशा complete binary tree होता है।
- यह heap को balanced और memory-efficient बनाता है।
2. Heap Property (Parent-Child Relationship)
- Heap में parent और child के बीच strict ordering होती है :
- Max Heap : Parent ≥ Child
- Min Heap : Parent ≤ Child
3. Efficient Max/Min Element Access
- Root node में हमेशा max (Max Heap) या min (Min Heap) element होता है। इसलिए O(1) time में maximum/minimum element access किया जा सकता है।
- Use Case : Priority Queue (IRCTC, Hospital ER), CPU Task Scheduling
4. Efficient Insertion & Deletion
- Heap में insert और delete operations O(log n) time में perform होते हैं।
5. Array-Based Implementation
- Heap को array में store किया जा सकता है।
- Indexing rules :
- Parent : { i }
- Left Child : { 2i + 1 }
- Right Child : { 2i + 2 }
6. Priority Management
- Heap का main advantage यह है कि यह priority-based task handling आसान बनाता है।
- Examples : CPU scheduling (high priority task first)
7. Useful for Heap Sort
- Heap की structure Heap Sort में efficient sorting के लिए perfect है।
- Max Heap से repeatedly max element remove करके ascending order achieve किया जा सकता है।
8. Balanced Memory Usage
- Complete binary tree होने से Heap balanced memory use करता है।
- Array representation में pointer overhead नहीं होता।
Heap operation
1. Insertion
- नया element हमेशा tree के last position पर add होता है।
- heap property maintain करने के लिए up-heap/bubble-up operation किया जाता है।
उदाहरण : Insert 60 in Max Heap
Before :
100
/ \
50 30
/ \ /
20 10 5
Add 60 at last position :
100
/ \
50 30
/ \ / \
20 10 5 60
Bubble-up operation : Swap 60 with 50
100
/ \
60 30
/ \ / \
20 10 5 50
2. Deletion
- Usually, root node (max/min) delete होता है।
- Last element root में move किया जाता है।
- down-heap/sift-down operation करके heap property maintain होती है।
उदाहरण : Delete root 100 from Max Heap
Before : 100
/ \
60 30
/ \ / \
20 10 5 50
Move last element 50 to root :
50
/ \
60 30
/ \ /
20 10 5
Sift-down operation : Swap 50 with 60
60
/ \
50 30
/ \ /
20 10 5
3. Heapify
Heapify एक process है, tree को heap property maintain करने का।
Two types :
- Top-down heapify (after deletion)
- Bottom-up heapify (after insertion)
Time Complexity : O(log n)
4. Build Heap
किसी array को heap में convert करना build heap कहलाता है।
Efficient method : Bottom-up heapify
Time Complexity : O(n)
Heap Applications (उपयोग)
1. Priority Queue Implementation
- Heap का सबसे बड़ा और सबसे practical उपयोग Priority Queue बनाने में होता है।
- Priority Queue एक ऐसी queue होती है, जहाँ element को उनकी priority के आधार पर access किया जाता है, न कि first-come-first-serve, basis पर।
2. Heap Sort Algorithm
- Heap के structure की वजह से sorting efficient तरीके से की जा सकती है।
- Heap Sort में बार-बार top element लेकर array को sort किया जाता है।
- Time complexity भी stable रहती है।
3. Graph Algorithms
- graph algorithms heap के बिना almost impossible हैं।
- Used in : Dijkstra’s Shortest Path, Prim’s Minimum Spanning Tree
- इन algorithms में बार-बार minimum distance या minimum edge cost चाहिए होती है, जो heap fastest देता है।
4. Memory Management
- Operating system में memory allocation और deallocation जैसी processes में heap structures का उपयोग किया जाता है।
- ये operations को predictable और fast बनाता है।
5. Scheduling Problems
- Heap का एक और बड़ा उपयोग Task Scheduling में है
- Examples : CPU task scheduling, Event scheduling systems
Advantages of Heap (लाभ)
- Root node पर हमेशा minimum या maximum value मिलती है |
- Priority Queue implement करने के लिए सबसे efficient data structure है।
- Insert और Delete दोनों operations O(log n) में पूरा हो जाते हैं, क्योंकि structure हमेशा balanced रहता है।
- Heap complete binary tree होता है, इसलिए हमेशा balanced structure मिलता है।
- Array-based implementation होने से memory usage कम होती है।
- Graph algorithms जैसे Dijkstra और Prim में fastest performance देता है।
- Real-time data tasks जैसे Top-K elements, running median में बहुत useful है।
- Heap Sort एक trusted, in-place, O(n log n) sorting technique है जिसे बड़े datasets पर भी stability और performance मिलती है।
- Dynamic workloads में भी structure जल्दी maintain हो जाता है|
Disadvantages of Heap (हानियाँ)
- Search operation बहुत slow है (O(n)), क्योंकि heap सिर्फ root को order में रखता है, बाकी elements arbitrary होते हैं।
- हर insertion या deletion के बाद heapify करना पड़ता है, जो time बढ़ा देता है।
- Heap में पूरा data sorted नहीं होता, सिर्फ root element ही guaranteed होता है।
- Implementation थोड़ा tricky है, normal binary tree या array की तरह plug-and-play नहीं।
- Heap Sort stable नहीं होता, इसलिए cases में Merge Sort और Quick Sort ज़्यादा बेहतर perform कर सकते हैं।
- बार-बार heapify की वजह से कभी-कभी cache performance भी hit हो सकती है।
- यह general-purpose searching या random-access tasks के लिए ideal नहीं है, यह strictly priority-based scenarios में best है।
