मैं मिनट-ढेर और अधिकतम-ढेर का अध्ययन किया है, और मैं सवालों की एक जोड़ी है:एक सॉर्टेड सरणी एक मिनी-ढेर है? अधिकतम-ढेर का न्यूनतम मूल्य क्या है?
सरणी-आधारित ढेर कार्यान्वयन का उपयोग करते समय निम्नतम से उच्चतम क्रमबद्ध एक सरणी एक न्यूनतम-ढेर है। ढेर संपत्ति जो माता-पिता नोड अपने बच्चों के नोड्स (2i + 1 और 2i + 2, शून्य-आधारित सरणी का उपयोग करके) से अधिक है, उन सभी नोड्स के लिए रखती है जिनमें बच्चे हैं।
अधिकतम ढेर का न्यूनतम मूल्य पत्ती नोड्स में से एक में है, लेकिन आप नहीं जानते कि कौन सा है। चूंकि न्यूनतम नोड परिभाषा के अनुसार, किसी भी बच्चे नोड्स नहीं कर सकता है, यह एक पत्ता होना चाहिए। हालांकि, ढेर संपत्ति यह निर्दिष्ट नहीं करती है कि कैसे पत्ती नोड एक दूसरे के साथ तुलना करते हैं, केवल उनके माता-पिता के साथ।
एक सॉर्टेड सरणी एक न्यूनतम-ढेर है?
हां, यदि आप ठेठ सरणी-संग्रहित ढेर सम्मेलन का उपयोग कर रहे हैं।
अधिकतम-ढेर का न्यूनतम मूल्य कहां है?
पत्तियों में से एक पर। जो बिल्कुल अनिर्धारित है।
आप इंडेक्स के लिए एक सरणी के रूप में बाइनरी ढेर को कार्यान्वित कर सकते हैं, मैं 2 * i + 1 और 2 * i + 2 (मैं 0 से शुरू होता हूं) के साथ तुलना करता हूं। मिनट में ढेर एक [i] < एक [2 * i + 1] और एक [i] < एक [2 * मैं + 2]
तो
1। एक क्रमबद्ध सरणी एक न्यूनतम ढेर है।
2। यह विशिष्ट सूचकांक नहीं है। सभी हम जानते हैं कि यह सिर्फ एक पत्ती
है कि मैं सुझाव है कि आप पढ़ा है इस http://en.wikipedia.org/wiki/Binary_heap
जहां एक अधिकतम ढेर के न्यूनतम मूल्य है?
उत्तर: अधिकतम ढेर का उपयोग करके सरणी को 1 से एन तक इंडेक्स से शुरू किया जा सकता है। पहला तत्व अधिकतम ढेर की जड़ है। ढेर संपत्ति: इंडेक्स पर नोड मैंने 2i पर सही बच्चा छोड़ा है और दाएं बच्चे को 2i + 1 पर छोड़ दिया है (यदि 2i और 2i + 1 ढेर आकार i.e. सरणी लंबाई से कम हैं)।
अधिकतम ढेर के लीफ नोड इंडेक्स i + 1 से n में पाए जाते हैं। यहां मैं = एन/2; एन सरणी लंबाई है। और पत्ती नोड्स में से एक न्यूनतम मूल्य है।
तो हम [i + 1] से [n] के मानों से अधिकतम ढेर का न्यूनतम मान पा सकते हैं। न्यूनतम मूल्य खोजने के लिए समय जटिलता ऑर्डर-ऑफ (एन-आई) है।
- एक सॉर्टेड सरणी एक न्यूनतम ढेर है?
यह आरोही आदेश दिया है - निम्नलिखित नियमों के साथ एक द्विआधारी ढेर के सरणी कार्यान्वयन - हाँ, आम तौर पर बोल रहा है यह एक मिनट ढेर, और अधिक स्पष्ट है:
एक ही समय में, यह रिवर्स में काम नहीं करता है - एक सरणी आधारित द्विआधारी ढेर एक संग्रहीत नहीं करेगा क्रमबद्ध सूची।
- अधिकतम ढेर का न्यूनतम मूल्य कहां है?
यह परिभाषित नहीं है, और यह सवाल है कि आप जल्दी से जवाब देने के लिए जब आप एक मिनट के ढेर में अपनी चाबी की दुकान चाहते हैं नहीं है। यदि आप ओ (1) समय में ढेर के अधिकतम और अधिकतम दोनों को देखने में सक्षम होना चाहते हैं, तो आप जावा में MinMaxPriorityQueue जैसे वर्गों का उपयोग कर सकते हैं।
एक सॉर्टेड सरणी एक न्यूनतम-ढेर है?
क्रमबद्ध सरणी या तो मिनट-ढेर या अधिकतम-ढेर है, लेकिन इसके विपरीत
मिनट-ढेर या अधिकतम-ढेर जरूरी सरणियों पृथक नहीं किया जा सच नहीं है।
अधिकतम-ढेर का न्यूनतम मूल्य क्या है?
परिभाषा द्वारा अधिकतम-ढेर (या प्राथमिकता कतार) ओ (1) समय में संग्रह से अधिकतम मूल्य प्रदान करता है। यदि किसी को अधिकतम-ढेर से न्यूनतम मूल्य पुनर्प्राप्त करने की आवश्यकता है तो इस समस्या के लिए पहले स्थान पर हीप का उपयोग करना सही नहीं है। ऐसा लगता है कि एक स्टैक फीफो एक्सेस प्रदान करने या लिफ्ट एक्सेस प्रदान करने के लिए कतार की अपेक्षा करने की अपेक्षा करता है।
लेकिन jfyi, न्यूनतम मूल्य ढेर द्वारा बनाए गए पेड़ की पत्तियों में से एक पर होगा। यह किसी भी subtree पर हो सकता है। इसलिए आपको एक और एल्गोरिदम चाहिए जो इसे ढूंढने के लिए ओ (1) समय से अधिक समय लेगा।
एक साइड नोट के रूप में:
एन तत्वों के साथ एक ढेर में [1 से (एन + 1)/2] पत्तियां हो सकती हैं।
तो पेड़ ढेर द्वारा गठित की ऊंचाई h फिर ढेर होगा तक 2^(ज -1) छोड़ देता है
सरणी को आरोही क्रम या अवरोही क्रम में सॉर्ट किया जा सकता है। कथन "एक क्रमबद्ध सरणी न्यूनतम-ढेर है" आंशिक रूप से सही है। इस कथन का सही संस्करण है "आरोही क्रम में क्रमबद्ध एक सरणी को मिनी-हीप के रूप में माना जा सकता है" और इसके पूरक कथन "अवरोही क्रम में क्रमबद्ध एक सरणी को अधिकतम ढेर के रूप में माना जा सकता है"।
"एक आरोही क्रम में सॉर्ट सरणी min- ढेर के रूप में इलाज किया जा सकता है" लेकिन याद है कि "सभी मिनट-ढेर आरोही क्रम में सॉर्ट सरणी का रूप ले सकता है।"
और अधिकतम ढेर के न्यूनतम मूल्य के बारे में हम केवल यह जानते हैं कि यह पत्तियों में मौजूद है और हम इसे खोज सकते हैं ओ (एन)