प्रश्न
insert, meld, find-min, extract-min, decrease-key और delete का समर्थन करने वाला एक Fibonacci Heap लागू करें। समझाएं कि root lists, parent-child लिंक्स, degree, mark bits और cascading cuts एक साथ कैसे काम करते हैं, और एक पोटेंशियल फ़ंक्शन का उपयोग करके दिखाएं कि क्यों insert, meld, find-min और decrease-key O(1) एमॉर्टाइज्ड हैं जबकि extract-min O(log n) एमॉर्टाइज्ड है।
इंटरव्यूअर क्या जांच रहा है
- क्या आप वास्तविक लागत (actual cost) और एमॉर्टाइज्ड लागत (amortized cost) के बीच अंतर करते हैं, बजाय इसके कि हर O(1) एमॉर्टाइज्ड ऑपरेशन को हमेशा O(1) कहें।
- क्या आप सर्कुलर डबली लिंक्ड लिस्ट्स (circular doubly linked lists), मिनिमम-रूट पॉइंटर, नोड हैंडल्स और पैरेंट पॉइंटर्स को सही ढंग से बनाए रखते हैं।
- क्या decrease-key सही तरीके से cuts, marking और cascading cuts निष्पादित करता है।
- क्या आप सैद्धांतिक लाभ, इंजीनियरिंग कॉन्सटेंट्स (constants) और pairing तथा binary heaps की तुलना में ट्रेड-ऑफ़ को समझा सकते हैं।
मॉडल उत्तर
एक Fibonacci Heap, हीप-ऑर्डर्ड ट्रीज़ (heap-ordered trees) का एक संग्रह है। रूट्स एक सर्कुलर डबली लिंक्ड लिस्ट बनाते हैं, और प्रत्येक नोड एक parent, child list, degree और mark bit स्टोर करता है। यह संरचना extract-min तक कंसोलिडेशन (consolidation) को टालती है, जब रूट्स को डिग्री के अनुसार लिंक किया जाता है।
insert रूट लिस्ट में एक नोड जोड़ता है और न्यूनतम को अपडेट करता है; meld दो रूट लिस्ट्स को जोड़ता (splice) है। यदि decrease-key हीप ऑर्डर का उल्लंघन करता है, तो नोड को उसके पैरेंट से काटें (cut) और इसे रूट लिस्ट में जोड़ें। यदि पैरेंट पहले ही एक चाइल्ड खो चुका है, तो पुनरावर्ती रूप से (recursively) एक cascading cut करें। एक मार्क यह रिकॉर्ड करता है कि क्या कोई नोड पहले ही एक चाइल्ड खो चुका है और यह कैस्केडिंग डैमेज को सीमित करता है।
extract-min न्यूनतम रूट के चिल्ड्रेन को रूट लिस्ट में प्रमोट करता है, उस रूट को हटाता है, और समान डिग्री वाले रूट्स को बार-बार लिंक करता है। एक सामान्य पोटेंशियल रूट्स की संख्या और मार्क्ड नोड्स की संख्या के दोगुने का योग होता है। Insert और meld रूट्स बढ़ाते हैं लेकिन केवल एक कॉन्सटेंट का भुगतान करते हैं; cascading cuts मार्क्ड नोड्स को कम करते हैं और पोटेंशियल द्वारा भुगतान किए जाते हैं। extract-min में लिंक्स की संख्या O(log n) द्वारा सीमित होती है क्योंकि हीप ऑर्डर अधिकतम डिग्री को सीमित करता है।
कार्यान्वयन रूपरेखा (Implementation sketch)
स्यूडोकोड महत्वपूर्ण decrease-key पाथ दिखाता है; कॉलर नोड हैंडल का मालिक होता है।
decreaseKey(x, newKey):
if newKey > x.key: error
x.key = newKey
p = x.parent
if p is not empty and x.key < p.key:
cut(x, p)
cascadingCut(p)
if x.key < min.key:
min = x
cut(x, p):
removeFromChildList(p, x)
p.degree -= 1
addToRootList(x)
x.parent = empty
x.mark = false
cascadingCut(y):
p = y.parent
if p is empty: return
if y.mark is false:
y.mark = true
else:
cut(y, p)
cascadingCut(p)extract-min के दौरान, न्यूनतम रूट को हटाने से पहले चिल्ड्रेन को प्रमोट करते समय सुरक्षित रूप से next पॉइंटर को सेव करें। समान डिग्री वाले रूट्स को लिंक करते समय parent, child, degree और mark को अपडेट करना आवश्यक है, जिसके बाद नए न्यूनतम के लिए स्कैन किया जाता है।
सामान्य गलतियाँ (Common pitfalls)
- ऐरे-आधारित बाइनरी हीप लिखना और यह दावा करना कि इसमें Fibonacci Heap जैसा O(1) एमॉर्टाइज्ड decrease-key है।
- कट के बाद parent या mark को साफ़ करना भूल जाना, जिससे अगला कैस्केड दूषित हो जाता है।
- एक अमान्य next पॉइंटर का उपयोग करते हुए सर्कुलर डबली लिंक्ड लिस्ट से डिलीट करना।
- extract-min के बाद केवल पुराने रूट्स की तुलना करना और रूट लिस्ट तथा मिनिमम स्कैन में प्रमोट किए गए चिल्ड्रेन को भूल जाना।
- केवल एसिम्प्टोटिक बाउंड्स (asymptotic bounds) की तुलना करना और पॉइंटर चेज़िंग, कैश लोकैलिटी, एलोकेशन और इम्प्लीमेंटेशन जटिलता को नज़रअंदाज़ करना।
जटिलता ट्रेड-ऑफ़ (Complexity trade-offs)
जब decrease-key बार-बार होता है, meld की आवश्यकता होती है, और एमॉर्टाइज्ड विश्लेषण स्वीकार्य होता है, तो Fibonacci Heap की एक आकर्षक सैद्धांतिक सीमा होती है; क्लासिक उदाहरण Prim's और Dijkstra's एल्गोरिदम के लिए बेहतर सीमाएं हैं। प्रोडक्शन में, pairing heaps, rank-pairing heaps, या binary heaps अक्सर बेहतर प्रतिस्पर्धा करते हैं क्योंकि वे सरल और अधिक कैश-फ्रेंडली होते हैं।
ये सीमाएं नोड हैंडल्स मानकर चलती हैं। यदि कॉलर केवल की (key) द्वारा नोड्स ढूंढ सकते हैं, तो एक सहायक इंडेक्स डिज़ाइन को बदल देता है। एक समवर्ती (concurrent) कार्यान्वयन को रूट लिस्ट्स और हैंडल्स के स्वामित्व को भी परिभाषित करना चाहिए; लॉक-फ्री सुरक्षा एमॉर्टाइज्ड विश्लेषण से स्वतः प्राप्त नहीं होती है।
एक सिंगलटन, डुप्लिकेट कीज़, खाली हीप के साथ meld, बार-बार decrease-key, और अंतिम नोड को डिलीट करने का परीक्षण करें। रैंडम ऑपरेशन सीक्वेंस उत्पन्न करें और संदर्भ प्रायोरिटी क्यू के साथ न्यूनतम मानों और extract-min क्रम की तुलना करें। एक ऐसा नोड बनाएं जो क्रम में दो चिल्ड्रेन खोता है ताकि यह सत्यापित किया जा सके कि पहला नुकसान इसे मार्क करता है और दूसरा नुकसान इसे काटता (cut) है।
संदर्भ (References)
- MIT OpenCourseWare Fibonacci heaps व्याख्यान: पोटेंशियल विश्लेषण और decrease-key/extract-min सीमाएं।
- Fibonacci Heaps Revisited: cascading cuts और एमॉर्टाइज्ड सीमाओं का पुनर्वparam/पुनर्विश्लेषण।
- Fredman और Tarjan का मूल पेपर: Fibonacci heaps और नेटवर्क ऑप्टिमाइज़ेशन एल्गोरिदम में उनका उपयोग।
फॉलो-अप प्रश्न
मार्क्ड नोड्स पोटेंशियल में दो इकाइयों का योगदान क्यों करते हैं?
एक cascading cut एक मार्क्ड नोड को हटाता है और एक रूट जोड़ता है। पोटेंशियल की दो इकाइयाँ मार्क को साफ़ करने और रूट को जोड़ने के लिए भुगतान करती हैं, जिससे पूरे कैस्केड की एमॉर्टाइज्ड लागत स्थिर (constant) रहती है।
extract-min O(log n) एमॉर्टाइज्ड क्यों है?
न्यूनतम को हटाने और उसके चिल्ड्रेन को प्रमोट करने के बाद, कंसोलिडेशन प्रति डिग्री अधिकतम एक रूट रखता है। हीप ऑर्डर किसी नोड की डिग्री को उसके सब-ट्री आकार से जोड़ता है, इसलिए अधिकतम डिग्री O(log n) होती है, जो लिंक्स की संख्या को सीमित करती है।
meld O(1) एमॉर्टाइज्ड क्यों हो सकता है?
दो सर्कुलर रूट लिस्ट्स को सीधे जोड़ा (splice) जा सकता है और उनके न्यूनतम पॉइंटर्स की तुलना की जा सकती है। समान डिग्री वाले ट्रीज़ को बाद के extract-min तक कंसोलिडेट नहीं किया जाता है।
बाइनरी हीप कब एक बेहतर विकल्प है?
बाइनरी हीप का उपयोग तब करें जब decrease-key दुर्लभ हो, ऐरे लोकैलिटी महत्वपूर्ण हो, नोड हैंडल्स असुविधाजनक हों, या टीम एक सरल कार्यान्वयन को महत्व देती हो। यह पूर्वानुमेय मेमोरी व्यवहार के साथ O(log n) ऑपरेशन्स प्रदान करता है।
आप delete को कैसे लागू करते हैं?
नोड की की (key) को ऋणात्मक अनंत (negative infinity) तक घटाएं और extract-min को कॉल करें। एक प्रोडक्शन कार्यान्वयन को की डोमेन, सेंटिनल व्यवहार और हैंडल अमान्यकरण को परिभाषित करना चाहिए ताकि एक वैध व्यावसायिक की को कभी भी सेंटिनल न समझा जाए।