डीएए - बाइनरी हीप

कई प्रकार के ढेर हैं, हालांकि इस अध्याय में, हम बाइनरी हीप पर चर्चा करने जा रहे हैं। एbinary heapएक डेटा संरचना है, जो पूर्ण बाइनरी ट्री के समान दिखता है। ढेर डेटा संरचना नीचे चर्चा की गई संपत्तियों के आदेश का पालन करती है। आम तौर पर, एक हीप को एक सरणी द्वारा दर्शाया जाता है। इस अध्याय में, हम एक ढेर का प्रतिनिधित्व कर रहे हैंH।

जैसा कि ढेर के तत्वों को एक सरणी में संग्रहीत किया जाता है, जैसा कि शुरुआती सूचकांक को देखते हुए 1के मूल नोड की स्थिति i^th तत्व पर पाया जा सकता है ⌊ i/2 ⌋। बायां बच्चा और दायां बच्चाi^th नोड स्थिति में है 2i तथा 2i + 1।

एक बाइनरी हीप को आगे भी वर्गीकृत किया जा सकता है max-heap या ए min-heap आदेश देने वाली संपत्ति के आधार पर।

अधिकतम ढेर

इस ढेर में, नोड का मुख्य मूल्य उच्चतम बच्चे के प्रमुख मूल्य से अधिक या उसके बराबर है।

अत, H[Parent(i)] ≥ H[i]

मिन-ढेर

मीन-हीप में, नोड का मुख्य मूल्य सबसे कम बच्चे के प्रमुख मूल्य से कम या बराबर होता है।

अत, H[Parent(i)] ≤ H[i]

इस संदर्भ में, बेसिक ऑपरेशन को मैक्स-हीप के संबंध में नीचे दिखाया गया है। हीप्स में और अंदर से तत्वों का सम्मिलन और विलोपन तत्वों के पुनर्व्यवस्था की आवश्यकता है। अत,Heapify फ़ंक्शन को कॉल करने की आवश्यकता है।

ऐरे प्रतिनिधित्व

एक पूर्ण द्विआधारी वृक्ष को एक सरणी द्वारा दर्शाया जा सकता है, अपने तत्वों को स्तर क्रम ट्रैवर्सल का उपयोग करके संग्रहीत करता है।

आइए हम एक ढेर पर विचार करें (जैसा कि नीचे दिखाया गया है) जिसे एक सरणी द्वारा दर्शाया जाएगा H।

के रूप में प्रारंभिक सूचकांक को ध्यान में रखते हुए 0, स्तर क्रम ट्रैवर्सल का उपयोग करते हुए, तत्वों को एक सरणी में निम्नानुसार रखा जा रहा है।

Index	0	1	2	3	4	5	6	7	8	...
elements	70	30	50	12	20	35	25	4	8	...

इस संदर्भ में, ढेर के संचालन को मैक्स-हीप के संबंध में दर्शाया जा रहा है।

सूचकांक में एक तत्व के माता-पिता के सूचकांक को खोजने के लिए iनिम्नलिखित एल्गोरिथ्म Parent (numbers[], i) प्रयोग किया जाता है।

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

सूचकांक में एक तत्व के बाएं बच्चे का सूचकांक i निम्नलिखित एल्गोरिथ्म का उपयोग करके पाया जा सकता है, Left-Child (numbers[], i)।

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL

सूचकांक में एक तत्व के सही बच्चे का सूचकांक i निम्नलिखित एल्गोरिथ्म का उपयोग करके पाया जा सकता है, Right-Child(numbers[], i)।

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL