अंतर

Question

दोनों std::priority_queue और std::set (और std::multiset) के बाद से डेटा कंटेनर है कि तत्वों की दुकान और आप उन्हें एक आदेश दिया फैशन में पहुंचने देते हैं, और एक ही प्रविष्टि जटिलता O(log n) है कर रहे हैं, क्या कर रहे हैं दूसरे पर एक का उपयोग करने के फायदे (या, किस तरह की स्थितियों में एक या दूसरे के लिए कॉल?)? उनके प्रदर्शन और विभिन्न उपयोगों के लिए उपयुक्तता

जबकि मुझे पता है कि अंतर्निहित संरचना अलग हैं, मैं नहीं के रूप में ज्यादा उनके कार्यान्वयन में अंतर करने में रुचि के रूप में मैं तुलना में हूँ कर रहा हूँ।

नोट: मुझे एक सेट में नो-डुप्लिकेट के बारे में पता है। यही कारण है कि मैंने std::multiset का भी उल्लेख किया क्योंकि इसका std::set जैसा ही व्यवहार है लेकिन इसका उपयोग किया जा सकता है जहां संग्रहीत डेटा को समान तत्वों की तुलना करने की अनुमति है। तो कृपया, एकल/एकाधिक कुंजी मुद्दे पर टिप्पणी न करें।

Answer 1

एक प्राथमिकता कतार केवल आप क्रमबद्ध क्रम में एक तत्व तक पहुँच देता है - यानी, आप सर्वोच्च प्राथमिकता आइटम प्राप्त कर सकते हैं, और जब आप कि निकालते हैं, तो आप अगले सर्वोच्च प्राथमिकता प्राप्त कर सकते हैं, और इसी तरह। एक प्राथमिकता कतार भी डुप्लिकेट तत्वों की अनुमति देती है, इसलिए यह एक सेट की तुलना में एक मल्टीसेट की तरह है। [संपादित करें: @Tadeusz कोपेक ने बताया, एक ढेर का निर्माण ढेर में वस्तुओं की संख्या पर भी रैखिक है, जहां एक सेट बनाना ओ (एन लॉग एन) है जब तक कि यह एक अनुक्रम से बनाया जा रहा है जो पहले से ही आदेश दिया गया है (इस मामले में यह भी रैखिक है)।

एक सेट आपको क्रमबद्ध क्रम में पूर्ण पहुंच की अनुमति देता है, उदाहरण के लिए, आप सेट के बीच में दो तत्वों को कहीं भी ढूंढ सकते हैं, फिर एक से दूसरे में क्रमबद्ध हो सकते हैं।

1. एक तत्व O(log n)
2. छोटी से छोटी तत्व O(1)
3. छोटी से छोटी तत्व O(log n)

डालें जाओ मिटा जबकि std::set है:

Answer 2

सेट/मल्टीसेट आमतौर पर एक बाइनरी पेड़ द्वारा समर्थित होते हैं। http://en.wikipedia.org/wiki/Binary_tree

प्राथमिकता_क्यू आमतौर पर एक ढेर द्वारा समर्थित है। http://en.wikipedia.org/wiki/Heap_(data_structure)

तो प्रश्न वास्तव में एक ढेर के बजाय बाइनरी पेड़ का उपयोग कब करना चाहिए?

दोनों संरचनाएं पेड़ में रखी जाती हैं, हालांकि उत्तरदाताओं के बीच संबंधों के नियम अलग-अलग होते हैं।

हम माता-पिता के लिए पद पी, बाएं बच्चे के लिए एल, और सही बच्चे के लिए आर कॉल करेंगे।

एक द्विआधारी पेड़ एल < पी < आर

एक ढेर पी < एल में और पी < आर

तो द्विआधारी पेड़ तरह "बग़ल में" और ढेर तरह "ऊपर की तरफ" में।

तो यदि हम इसे बाइनरी पेड़ एल, पी, आर की तुलना में त्रिकोण के रूप में देखते हैं तो पूरी तरह से हल हो जाते हैं, जबकि ढेर में एल और आर के बीच संबंध अज्ञात है (केवल पी के साथ उनका संबंध)।

यह निम्न प्रभाव होते हैं:

• आप एक अवर्गीकृत सरणी है और यह एक द्विआधारी पेड़ में चालू करना चाहते हैं यह O(nlogn) समय लगता है। यदि आप इसे एक ढेर में बदलना चाहते हैं तो यह केवल O(n) समय लेता है, (क्योंकि यह केवल चरम तत्व को खोजने के लिए तुलना करता है)

• हीप्स अधिक कुशल हैं यदि आपको केवल चरम तत्व की आवश्यकता है (कुछ तुलनात्मक कार्य से सबसे कम या उच्चतम)। ढेर केवल चरम तत्व को निर्धारित करने के लिए आवश्यक तुलना (आलसी) करते हैं।

• बाइनरी पेड़ पूरे संग्रह को ऑर्डर करने के लिए आवश्यक तुलना करते हैं, और पूरे संग्रह को हर समय क्रमबद्ध करते हैं।

• ढेर में निम्नतम तत्व के निरंतर समय की लुकअप (चोटी) होती है, बाइनरी पेड़ों में निम्नतम तत्व की लॉगरिदमिक टाइम लुकअप होती है।

Answer 3

std::priority_queue निम्न कार्य करने की अनुमति देता हैअधिक संभावनाएं:

1. सम्मिलित किसी भी तत्व O(log n) और निरंतर std::priority_queue
2. में से अधिक है का पता लगाएं किसी भी तत्व O(log n)
3. एक तत्व का पता लगाएं,> = एक अपने O(log n) लिए देख रहे हैं (lower_bound) की तुलना में
4. मिटाएं क्रमबद्ध आदेश 012 में पिछली/अगली तत्व के लिए किसी भी तत्व O(log n)
5. ले जाएँ
6. जाओ छोटी से छोटी तत्व O(1)
7. सबसे बड़ा तत्व O(1)

Answer 4

के बाद से प्राप्त दोनों std::priority_queue और std::set (और std::multiset) डेटा कंटेनर है कि तत्वों की दुकान और आप उन्हें का उपयोग करने की अनुमति देते हैं एक आदेशित फैशन में, और एक ही सम्मिलन जटिलता O(log n) है, दूसरे पर एक का उपयोग करने के फायदे क्या हैं (या, किस तरह की स्थितियों में से एक के लिए कॉल करें या अन्य?)?

हालांकि डालने और मिटा दोनों कंटेनरों के लिए संचालन एक ही जटिलता है हे (लॉग एन), एसटीडी के लिए इन आपरेशनों :: सेट एसटीडी के लिए की तुलना में धीमी कर रहे हैं :: priority_queue । ऐसा इसलिए है क्योंकि std :: सेट कई स्मृति आवंटन करता है।std :: सेट के प्रत्येक तत्व को अपने आवंटन में संग्रहीत किया जाता है। std :: priority_queue (अंडरलेइंग std :: वेक्टर डिफ़ॉल्ट रूप से कंटेनर के साथ) सभी तत्वों को स्टोर करने के लिए एकल आवंटन का उपयोग करता है। दूसरी ओर std :: priority_queue अपने तत्वों पर कई स्वैप संचालन का उपयोग करता है जबकि std :: set केवल पॉइंटर्स स्वैपिंग का उपयोग करता है। तो यदि स्वैपिंग तत्व प्रकार के लिए बहुत धीमी गति से ऑपरेशन है, तो std :: set का उपयोग करके अधिक कुशल हो सकता है। इसके अलावा तत्व बिल्कुल गैर-स्वीकार्य हो सकता है।

std :: सेट के लिए मेमोरी ओवरहेड बहुत बड़ा है क्योंकि इसे अपने नोड्स के बीच कई पॉइंटर्स स्टोर करना पड़ता है।