मेरे पास एक वेक्टर है जिसे मैं ढेर बनाने के लिए उपयोग करना चाहता हूं। मुझे यकीन नहीं है कि मुझे C++ make_heap फ़ंक्शन का उपयोग करना चाहिए या मेरे वेक्टर को प्राथमिकता कतार में रखना चाहिए? प्रदर्शन के मामले में कौन सा बेहतर है? मुझे एक बनाम दूसरे का उपयोग कब करना चाहिए?मुझे make_heap बनाम प्राथमिकता कतार का उपयोग कब करना चाहिए?
प्रदर्शन के थर्म में कोई अंतर नहीं है। std::priority_queue केवल एक एडाप्टर क्लास है जो कंटेनर को लपेटता है और एक ही ढेर से संबंधित फ़ंक्शन को कक्षा में कॉल करता है। std::priority_queue का विनिर्देश स्पष्ट रूप से बताता है कि।
एक उजागर std::vector (ढेर से संबंधित कार्यों को सीधे कॉल करके) से ढेर-आधारित प्राथमिकता कतार का निर्माण करके आप इसे बाहरी पहुंच की संभावना के लिए खोलते हैं, संभावित रूप से ढेर/कतार की अखंडता को नुकसान पहुंचाते हैं। std::priority_queue एक बाधा के रूप में कार्य करता है जो न्यूनतम "0on, pop(), top() आदि तक पहुंच प्रदान करता है। आप इसे आत्म-अनुशासन लागू करने के उपाय के रूप में देख सकते हैं।
इसके अलावा, अपने कतार इंटरफ़ेस को संचालन के "कैननिकल" सेट में अपनाने के द्वारा, आप इसे समान बाहरी विनिर्देश के अनुरूप प्राथमिकता कतारों के अन्य वर्ग-आधारित कार्यान्वयन के साथ समान और अदला-बदले बनाते हैं।
एक प्राथमिकता_क्यू (कम से कम सामान्य रूप से) एक ढेर के रूप में लागू होती है। इस प्रकार, असली सवाल यह है कि क्या प्राथमिकता_क्यू आपको जो चाहिए वह प्रदान करता है। जब आप make_heap का उपयोग करते हैं तो आपके पास अभी भी सभी तत्वों तक पहुंच है। जब आप प्राथमिकता_क्यू का उपयोग करते हैं, तो आपके पास केवल कुछ ही ऑपरेशन होते हैं जो तत्वों तक सीमित पहुंच प्रदान करते हैं (मूल रूप से केवल एक आइटम डालें, और कतार के सिर पर आइटम को हटा दें)।
priority_queue कंटेनर नहीं है। यह एक कंटेनर एडाप्टर है जो एक विशिष्ट अंतर्निहित कंटेनर का उपयोग करता है, उदा। vector या deque, और डेटा के साथ काम करने के तरीकों का एक विशिष्ट सेट प्रदान करता है। इसके अलावा, इसका कार्यान्वयन *_heap एल्गोरिदम पर निर्भर करता है।
उदाहरण के लिए, जब भी आप vector पर कोई नया मान डालते हैं तो आपको एक ढेर के रूप में माना जाने वाला श्रेणी बढ़ाने के लिए push_heap पर कॉल करना चाहिए। यदि आप priority_queue का उपयोग नहीं करते हैं, तो यह आपको एक हीप (std::make_heap(v.begin(), v.begin() + (v.size()/2))) के रूप में vector का आधा मानने की अनुमति देता है, जबकि दूसरा आधा उतना ही होगा।
क्या priority_queue करता है जब आप इसे पर push फोन: यह अंतर्निहित कंटेनर के पीछे से एक नए तत्व धक्का और push_heap कॉल (यह केवल पहला तत्व मायने रखती है सबसे बड़ी होने के लिए) ढेर संपत्ति प्राथमिकता के आधार पर रखने के लिए।
मैं कहूंगा कि आप प्रदर्शन समस्याओं के बजाय समाधान डिजाइन और आपकी विशिष्ट आवश्यकताओं पर बेहतर विचार करेंगे।
यदि आप उस वेक्टर को संशोधित नहीं करना चाहते हैं तो आपको प्राथमिक कतार का उपयोग करना चाहिए क्योंकि यह एक अलग वेक्टर बनाता है (अतिरिक्त स्थान की आवश्यकता है)। इसके अलावा, इसे लागू करना आसान है। उदाहरण के लिए, जब आप किसी तत्व को पॉप करते समय make_heap का उपयोग करते हैं तो आपको दो कमांड का उपयोग करना होगा, पहले pop_heap और फिर pop_back .. लेकिन प्राथमिकता कतार के मामले में आप इसे केवल एक कमांड के साथ कर सकते हैं। इसी तरह, तत्व को ढेर में दबाते समय।
अब, दोनों का प्रदर्शन समान होगा क्योंकि प्राथमिकता कतार एक कंटेनर नहीं है और यह कुछ अंतर्निहित कंटेनर का उपयोग वेक्टर या डेक के रूप में करता है जो मेक_हेप ऑपरेशंस द्वारा उपयोग किए जाने वाले समान हीप ऑपरेशंस का उपयोग करता है .. इसलिए, आपको अपनी आवश्यकता के आधार पर एक का उपयोग करना चाहिए ।
अच्छी तरह से, यदि आप एक ढेर चाहते हैं, तो आपको इसे एक ढेर में बनाना चाहिए। प्राथमिकता कतार सभी ढेर नहीं हैं। ढेर बेहतर प्रदर्शन करते हैं। – Wug