निम्न समस्या को देखते हुए, मैं अपने वर्तमान समाधान के साथ पूरी तरह से यकीन नहीं है:ओ (के * लॉग (के)) में दिए गए ढेर में सबसे बड़े के तत्व मुद्रित करें?
प्रश्न:
n तत्व है, जो एक सरणी A में संग्रहित है के साथ एक अधिकतम ढेर को देखते हुए यह संभव करने के लिए है O(K*log(K)) में सभी सबसे बड़े K तत्वों को मुद्रित करें?
मेरा जवाब:
हाँ, यह है, क्योंकि एक तत्व खोज O(log(K)) की आवश्यकता है, इसलिए कर रही है कि
K तत्वों के लिए
O(K * log(K)) चल समय लगेगा।
यह अधिकतम-ढेर में संभव है क्योंकि आप केवल पेड़ से तत्वों को प्रिंट कर रहे हैं, उन्हें निकालने नहीं।
रूट नोड पर स्थित अधिकतम तत्व की पहचान करके प्रारंभ करें। एक नोड को एक पॉइंटर बनाएं और इसे अन्यथा खाली "अधिकतम" सूची में जोड़ें।फिर, k मानों में से प्रत्येक के लिए, लूप में निम्न चरणों का पालन करें।
कुल मिलाकर, रन टाइम ओ (klog (k)) वांछित है।
क्या ओ (लॉग (के)) समय में तीसरा कदम संभव होगा? यदि डेटा संरचना एक लिंक्ड सूची है, तो बाइनरी खोज संभव नहीं होगी (कम से कम लॉग (के) समय में संभव नहीं है)? यदि डेटा संरचना एक सरणी है, तो सम्मिलन ओ (1) नहीं होगा। अगर मुझे कुछ याद आया तो कृपया मुझे सही करें। –
मुझे लगता है कि तत्वों को पहले एक सरणी में कॉपी करना बेहतर होगा और फिर सरणी को सॉर्ट करें। –
@ShubhamGoyal डेटा संरचना एक ढेर हो सकती है, जो ओ (लॉग के) डालने और हटाने-अधिकतम का समर्थन करता है। सहमत हुए कि जवाब में व्यक्तिगत दावों ने परिचालन की जटिलता को –
दरअसल, यह बहुत आसान है, अधिकतम तत्व निकालने O(log(N)) है जहां N ढेर का आकार है। और N≠K।
मैं जोड़ता हूं कि यादृच्छिक तत्व की खोज O(N) है और O(Log(N)) नहीं है, लेकिन इस मामले में हम अधिकतम निकालना चाहते हैं।
आकार एन के ढेर में तत्व की खोज करना ओ (के) नहीं है। सबसे पहले, यह समझ में नहीं आता है कि एक तत्व खोजने के लिए समय जटिलता उन तत्वों की संख्या पर निर्भर करती है जिन्हें आप निकालने का प्रयास कर रहे हैं (जो कि के प्रतिनिधित्व करता है)। साथ ही, हेप — में खोज करने जैसी कोई चीज नहीं है जब तक कि आप O (N) में मानक लुक-ए-----तत्व खोज को गिनें।
हालांकि, ढेर में सबसे बड़ा तत्व ढूंढना ओ (1) डिज़ाइन द्वारा है (मुझे लगता है कि यह अधिकतम-ढेर है, इसलिए अधिकतम तत्व ढेर के शीर्ष पर है), और सबसे बड़ा तत्व निकालना आकार एन के ढेर से ओ (लॉग (एन)) (इसे एक पत्ता तत्व के साथ प्रतिस्थापित करें, और उस पत्ते को ढेर के नीचे वापस लेना चाहिए)।
तो, एक हीप, से के तत्वों को निकालने और गैर-निकाले गए तत्वों के ढेर को वापस करने के लिए, ओ (के और मिडॉट; लॉग (एन)) समय लेगा।
क्या होता है यदि आप के तत्वों को ढेर से गैर विनाशकारी निकालें तो क्या होता है? आप ढेर-ढेर को रखकर ऐसा कर सकते हैं (जहां एक ढेर का मूल्य उसके अधिकतम तत्व का मान है)। प्रारंभ में, इस ढेर के ढेर में केवल एक तत्व होता है (मूल ढेर)। अगले अधिकतम तत्व निकालने के लिए, आप शीर्ष ढेर निकालें, अपने शीर्ष तत्व निकालें (जो अधिकतम है) और उसके बाद दो उप-ढेर को ढेर में ढेर में दोबारा डालें।
यह हर हटाने (एक निकालने के लिए, दो को जोड़ने), जिसका अर्थ है यह कश्मीर तत्वों में पिरोना कभी नहीं होगा पर एक के बाद ढेर-के-ढेर बढ़ता है, और इसलिए निकालें-एक एड-दो ले जाएगा हे (लॉग (कश्मीर))। इसे Iterate, और आपको एक वास्तविक ओ (के & मिडॉट; लॉग (के)) एल्गोरिदम मिलता है जो शीर्ष के तत्वों को वापस करता है, लेकिन गैर-निकाले गए तत्वों के ढेर को वापस करने में असमर्थ है।
It is a simple and elegant algorithm to get first k elements of a max heap in k log(k) time.
steps:-
1.construct another max heap name it auxiliary heap
2.add root element of main heap to auxiliary heap
3.pop out the element from auxiliary heap and add it's 2 children to the heap
4.do step 2 and 3 till k elements have been popped out from auxiliary heap. Add the popped element's children to the auxiliary heap.
मुझे अन्य उत्तरों उलझन में मिला, इसलिए मैंने इसे वास्तविक उदाहरण ढेर के साथ समझाया। मान लें कि मूल ढेर आकार एन है और आप kth सबसे बड़े तत्वों को ढूंढना चाहते हैं, यह समाधान O (klogk) समय और O (k) स्थान लेता है।
10
/\
5 3
/\ /\
4 1 2 0
Original Heap, N = 7
5 वां सबसे बड़ा तत्व ढूंढना चाहते हैं। के = 5 नोट: नए ढेर में, आपको पॉइंटर को मूल ढेर में स्टोर करने की आवश्यकता है। इसका मतलब है, आप मूल ढेर को हटा या परिवर्तित नहीं करते हैं। मूल ढेर केवल पढ़ने के लिए है। इसलिए, आपको कभी भी ऐसे ऑपरेशन नहीं करना पड़ता है जिनके लिए ओ (लॉगएन) समय की आवश्यकता होती है।
एक्स को मूल ढेर में एक्स मानने के लिए पॉइंटर होने दें।
1 पुनरावृत्ति: नई ढेर में रूट नोड के सूचक जाओ
चरण 1: जोड़े सूचक नोड के लिए 10
10'
New Heap, size = 1, root = 10', root->left = 5, root right->3
प्रिंट 1st सबसे बड़ा तत्व = 10
2 यात्रा: का संदर्भ लें मूल ढेर और अपने बच्चों को नए ढेर में डालें। (पॉइंटर्स को स्टोर करना और मूल्य खुद नहीं)। पॉइंटर को स्टोर करने का कारण यह है कि आप मूल ढेर से ओ (एन) में उन तक पहुंच सकते हैं ताकि ओ (एन) के बजाय अपने बच्चों को खोज सकें ताकि यह पता चल सके कि वह मान मूल ढेर में कहां स्थित है।
चरण 2 ए: मूल ढेर से नए ढेर के रूट नोड के बाएं बच्चे की तलाश करें। नए ढेर में बाएं बच्चे (इस मामले में, 5 ') के लिए एक सूचक जोड़ें।
10'
/
5'
New Heap, size = 2, root = 10', root->left = 5, root right->3
चरण 2 बी: मूल ढेर से नए ढेर के रूट नोड के सही बच्चे की तलाश करें। नए ढेर में बाएं बच्चे (इस मामले में, 3 ') के लिए एक सूचक जोड़ें।
10'
/\
5' 3'
New Heap, size = 3, root = 10', root->left = 5, root right->3
चरण 2 सी: नए हीप से रूट नोड निकालें।
10' swap 3' remove & bubble 5'
/\ => /\ => /
5' 3' 5' 10' 3'
New Heap, size = 2, root = 5', root->left = 4, root right->1
प्रिंट (दाएं सबसे छोड़ देते हैं, वर्तमान जड़ नीचे रूट नोड और बुलबुला हटाने ढेर संपत्ति बनाए रखने के लिए के साथ स्वैप अधिकतम नोड) 2nd सबसे बड़ा तत्व = 5
चरण 3a: जड़ के बाईं बच्चे के लिए देखो मूल ढेर से नए ढेर का नोड। नए ढेर में बाएं बच्चे (इस मामले में, 4 ') के लिए एक सूचक जोड़ें।
5'
/\
3' 4'
New Heap, size = 3, root = 5', root->left = 4, root right->1
चरण 3 बी: मूल ढेर से नए ढेर के रूट नोड के सही बच्चे की तलाश करें। नए ढेर में बाएं बच्चे (इस मामले में, 1 ') के लिए एक सूचक जोड़ें।
5'
/\
3' 4'
/
1'
New Heap, size = 4, root = 5', root->left = 4, root right->1
चरण 3 सी: न्यू हीप से रूट नोड निकालें। (नया ढेर से स्वैप अधिकतम नोड (5 ') अपने अधिकार के साथ नई ढेर के सबसे मूल ढेर (1 से छोड़'), वर्तमान जड़ नीचे रूट नोड और बबल को दूर बनाए रखने के लिए ढेर संपत्ति)
5' Swap 1' remove & bubble 4'
/\ => /\ => /\
3' 4' 3' 4' 3' 1'
/ /
1' 5'
New Heap, size = 3, root = 4', root->left = NULL, root right->NULL
तीसरा सबसे बड़ा तत्व = 4
चरण 4 ए & चरण 4 बी कुछ भी नहीं करता है क्योंकि रूट नोड में इस मामले में मूल ढेर से कोई बच्चा नहीं है।
चरण 4 सी: नए हीप से रूट नोड निकालें।
4' Swap 1' remove & bubble 3'
/\ => /\ => /
3' 1' 3' 4' 1'
New Heap, size = 2, root = 3', root->left = 2, root right->0
प्रिंट 4 सबसे बड़ा तत्व = 3
चरण 5a (के साथ सही सबसे छोड़ देते हैं, वर्तमान जड़ नीचे रूट नोड और बुलबुला हटाने न्यू ढेर में ढेर संपत्ति बनाए रखने के लिए स्वैप अधिकतम नोड): बाएं के लिए देखो मूल ढेर से नए ढेर के रूट नोड के बच्चे। नए ढेर में बाएं बच्चे (इस मामले में, 2 ') के लिए एक सूचक जोड़ें।
3'
/\
1' 2'
New Heap, size = 3, root = 3', root->left = 2, root right->0
चरण 5 बी: मूल ढेर से नए ढेर के रूट नोड के सही बच्चे की तलाश करें। बाएं बच्चे के लिए एक सूचक (इस मामले में, 0 ') को नए ढेर में जोड़ें।
3'
/\
1' 2'
/
0'
New Heap, size = 4, root = 3', root->left = 2, root right->0
चरण 5 सी: नई ढेर से रूट नोड निकालें। (स्वैप अधिकतम नोड (3, न्यू ढेर में) ') अपने अधिकार अधिकांश के साथ (जो 0 है मूल ढेर से छोड़' वर्तमान जड़ नीचे रूट नोड और बुलबुला हटाने न्यू ढेर में ढेर संपत्ति बनाए रखने के लिए)
3' Swap 0' Remove & Bubble 2'
/\ => /\ => /\
1' 2' 1' 2' 1' 0'
/ /
0' 3'
New Heap, size = 3, root = 2', root->left = NULL, root->right = NULL
5 वें सबसे बड़े तत्व = 2
अंत में, चूंकि हम के पुनरावृत्तियों के माध्यम से चले गए हैं, के = 5. हम अब नए तत्व से रूट तत्व के मूल्य को निकाल सकते हैं। इस मामले में, मान 2. इसलिए है, इसलिए हमने मूल ढेर से केएचटी का सबसे बड़ा मूल्य पाया है।
समय जटिलता, टी (एन, कश्मीर) = ओ (klogk) अंतरिक्ष जटिलता, एस (एन, कश्मीर) = हे (के)
आशा इस मदद करता है!
जल्द ही ची लूंग,
टोरंटो विश्वविद्यालय।
चरण 3 सी और 5 सी में आपने सही पत्ते के साथ अधिकतम नोड स्वैप किया लेकिन आपने इसे सबसे अधिक पत्ते से बदल दिया? – user881300
@ user881300 मूल ढेर से सही सबसे पत्ता। धन्यवाद, मेरी व्याख्या में स्पष्ट होगा। –
[ओ (klogk) समय एल्गोरिदम का संभव डुप्लिकेट बाइनरी ढेर से केथ सबसे छोटा तत्व खोजने के लिए] (http://stackoverflow.com/questions/7650917/oklogk-time-algorithm-to-find-kth-smallest- तत्व-से-एक द्विआधारी-ढेर)। हो सकता है कि एक डुप्ली न हो, क्योंकि जुड़ा हुआ प्रश्न kth तत्व के लिए पूछता है, न कि सबसे महत्वपूर्ण तत्वों की सूची, लेकिन विचार समान है। – amit