अधिकतम BST बनाम संतुलित BST का उपयोग कर प्राथमिकता कतार को लागू करना
बैलेंस्ड BST और अधिकतम हीप दोनों सम्मिलित प्रदर्शन करते हैं और अंदर हटाते हैं O(logn)। हालांकि, एक अधिकतम हीप में अधिकतम मूल्य का पता लगाना है, O(1)लेकिन यह O(logn)संतुलित बीएसटी में है।
यदि हम एक अधिकतम ढेर में अधिकतम मूल्य निकालते हैं, O(logn)तो यह एक ऑपरेशन है।
संतुलित BST में, अधिकतम तत्व हटाना = अधिकतम मूल्य + हटाना; यह logn के बराबर होता है + logn कम हो जाता है O(logn)। यहां तक कि संतुलित BST में अधिकतम मूल्य को हटाना है O(logn)।
मैंने पढ़ा है कि अधिकतम हीप का ऐसा एक अनुप्रयोग एक प्राथमिकता कतार है और इसका मुख्य उद्देश्य प्रत्येक डॉक्यू ऑपरेशन के लिए अधिकतम मूल्य निकालना है। यदि अधिकतम तत्व को हटाना अधिकतम O(logn)हीप और संतुलित BST दोनों के लिए है, तो मेरे पास निम्नलिखित प्रश्न हैं
प्राथमिकता कतार में अधिकतम ढेर का उद्देश्य सिर्फ इसलिए है क्योंकि पूर्ण खोजे जाने वाले संतुलित बीएसटी का उपयोग करने के बजाय इसे लागू करना आसान है?
चूंकि कोई संतुलन कारक गणना नहीं है, इसलिए अधिकतम ढेर को असंतुलित बाइनरी ट्री कहा जा सकता है?
हर संतुलित BST को एक प्राथमिकता कतार के रूप में इस्तेमाल किया जा सकता है और जो कि
O(logn)अधिकतम ढेर खोजO(n)सही है, में भी खोज योग्य है?
सभी समय जटिलताओं की गणना सबसे खराब स्थिति के लिए की जाती है। कोई भी मदद बहुत ही सराहनीय होगी।
जवाब
प्राथमिकता कतार में अधिकतम ढेर का उद्देश्य सिर्फ इसलिए है क्योंकि पूर्ण खोजे जाने वाले संतुलित बीएसटी का उपयोग करने के बजाय इसे लागू करना आसान है?
ढेर के कुछ फायदे हैं:
एक अनियोजित इनपुट सरणी को देखते हुए, एक ढेर को अभी भी O (n) समय में बनाया जा सकता है , जबकि BST को O (nlogn) समय की आवश्यकता होती है ।
यदि प्रारंभिक इनपुट एक सरणी है, तो वही सरणी ढेर के रूप में काम कर सकती है, जिसका अर्थ है कि इसके लिए कोई अतिरिक्त मेमोरी की आवश्यकता नहीं है। यद्यपि कोई एरे में डेटा का उपयोग करके बीएसटी बनाने के तरीकों के बारे में सोच सकता है, यह काफी विषम (आदिम प्रकारों के लिए) होगा और अधिक प्रसंस्करण ओवरहेड देगा। एक BST आमतौर पर स्क्रैच से बनाया जाता है, डेटा को नोड्स में कॉपी करते हैं जैसे वे बनाए जाते हैं।
दिलचस्प तथ्य: एक सॉर्ट किया गया सरणी भी एक ढेर है, इसलिए यदि यह ज्ञात है कि इनपुट सॉर्ट किया गया है, तो ढेर बनाने के लिए कुछ भी करने की आवश्यकता नहीं है।
क्रॉस संदर्भों की आवश्यकता के बिना ढेर को एक सरणी के रूप में संग्रहीत किया जा सकता है , जबकि एक बीएसटी में आमतौर पर बाएं और दाएं संदर्भ के साथ नोड होते हैं। इसके कम से कम दो परिणाम हैं:
- BST के लिए उपयोग की जाने वाली मेमोरी ढेर के लिए लगभग 3 गुना अधिक है।
- हालाँकि कई कार्यों में हीप और BST दोनों के लिए एक ही समय की जटिलता होती है, लेकिन BST को अपनाने के लिए ओवरहेड बहुत अधिक होता है, जिससे कि इन कार्यों पर खर्च किया जाने वाला वास्तविक समय BST मामले में अधिक (स्थिर) कारक होता है।
चूंकि कोई संतुलन कारक गणना नहीं है, इसलिए अधिकतम ढेर को असंतुलित बाइनरी ट्री कहा जा सकता है?
एक ढेर वास्तव में एक पूर्ण बाइनरी ट्री है , इसलिए यह हमेशा उतना ही संतुलित होता है जितना कि यह हो सकता है: पत्तियां हमेशा अंतिम या एक-लेकिन-अंतिम स्तर में तैनात रहेंगी। एक आत्म-संतुलन BST (जैसे AVL, लाल-काला, ...) संतुलन के उस उच्च स्तर को नहीं हरा सकता है, जहां आपके पास अक्सर तीन स्तरों या उससे अधिक पर होने वाले पत्ते होंगे।
हर संतुलित BST को एक प्राथमिकता कतार के रूप में इस्तेमाल किया जा सकता है और जो O (logn) में खोजा जा सकता है लेकिन अधिकतम हीप खोज O (n) सही है?
हां यह सच है। इसलिए यदि एप्लिकेशन को खोज सुविधा की आवश्यकता है, तो एक BST श्रेष्ठ है।
प्राथमिकता कतार में अधिकतम ढेर का उद्देश्य सिर्फ इसलिए है क्योंकि पूर्ण खोजे जाने वाले संतुलित बीएसटी का उपयोग करने के बजाय इसे लागू करना आसान है?
नहीं। मैक्स हीप बेहतर तरीके से फिट बैठता है, क्योंकि यह ओ (1) समय में, ASAP के तत्व (प्राथमिकता का सम्मान करते हुए) वापस लौटने के लिए सावधानीपूर्वक किया जाता है। यही कारण है कि आप सबसे सरल संभव प्राथमिकता कतार से चाहते हैं।
चूंकि कोई संतुलन कारक गणना नहीं है, इसलिए अधिकतम ढेर को असंतुलित बाइनरी ट्री कहा जा सकता है?
नहीं। एक संतुलन भी है। लंबी कहानी छोटी, एक ढेर को संतुलित करना शिफ्ट-अप या शिफ्ट-डाउन ऑपरेशन (स्वैपिंग तत्व जो ऑर्डर से बाहर हैं) द्वारा किया जाता है।
हर संतुलित BST को एक प्राथमिकता कतार के रूप में इस्तेमाल किया जा सकता है और जो O (logn) में खोजा जा सकता है लेकिन अधिकतम हीप खोज O (n) सही है?
हाँ! साथ ही लिंक की गई सूची का उपयोग किया जा सकता है या सरणी। यह ओ-नोटेशन के संदर्भ में अधिक महंगा है और अभ्यास पर बहुत धीमा है।