प्राथमिकता कतार संरचना का उपयोग किया जाता है?

Question

सी ++ मानक पुस्तकालय प्रलेखन में कुछ कार्यों की खोज करते समय मैंने पढ़ा कि प्राथमिकता कतारों के लिए पुश और पॉप को निरंतर समय की आवश्यकता है।

http://www.cplusplus.com/reference/stl/priority_queue/push/

लगातार (priority_queue में)। हालांकि ध्यान दें कि पुश_हेप लॉगरिदमिक समय में काम करता है।

मेरा प्रश्न यह है कि पुश और पॉप के लिए ओ (1) के साथ प्राथमिकता कतार बनाए रखने के लिए किस प्रकार की डेटा संरचना का उपयोग किया जाता है?

Answer 1

मुझे लगता है कि है आप cplusplus.com's page का जिक्र कर रहे हैं।

इस सदस्य समारोह को प्रभावी ढंग से अंतर्निहित कंटेनर वस्तु के सदस्य समारोह push_back कहता है, और उसके बाद push_heap एल्गोरिथ्म कॉल priority_queues के ढेर संपत्ति रखने के लिए:

पेज यह कहता है पर इससे पहले

।

तो, O(1) धक्का के बाद, डेटा संरचना अपने ढेर संपत्ति अपरिवर्तनीय खो दिया है और उसके बाद हमेशा उस का पालन करेंगे एक O(log N) कॉल साथ कि संपत्ति को बहाल करने की। दूसरे शब्दों में, O(1) ऑपरेशन पूरे ऑपरेशन का केवल एक हिस्सा है; पूर्ण ऑपरेशन O(1) + O(log N) है जो O(log N) जैसा ही है।

मुझे लगता है कि वे उल्लेख करते हैं कि प्राथमिकता कतार एक एडाप्टर है और वे अंतर्निहित कंटेनर बनाम एडाप्टर क्या करता है के बीच के अंतर पर जोर देने की कोशिश कर रहे हैं।

Answer 2

पुश और लघुगणक समय में पॉप रन

http://www.cppreference.com/wiki/stl/priority_queue/pop

http://www.cppreference.com/wiki/stl/priority_queue/push

Answer 3

मैं हे (1) का दावा है ... जहां आप इसे देखा था के बारे में उलझन में हूँ के अनुसार?

किसी भी मामले में, यहां some notes on gcc's implementation of a priority queue हैं।

Answer 4

ऐसे प्रकार का ढेर नहीं है। उन्होंने लिखा है कि यह push_heap को कॉल करता है जो लॉगरिदमिक है इसलिए यह लॉगऑन है।

Answer 5

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

Answer 6

मानक push_heap और pop_heap, जो compilexity का तात्पर्य के मामले में उन सदस्यों को परिभाषित करता है संदेह है।

यदि that reference कहते हैं सच है (यह कहते top भी स्थिर है), क्यों किसी को भी लागू नहीं करता है सामान्य प्रयोजन हे (एन) std::priority_queue का उपयोग कर छँटाई?

दूसरा हालांकि, यह क्या संदर्भ कहने की कोशिश कर किया जा सकता है, एक बहुत ही भ्रामक तरह से है: जटिलता के push_back हे (1) + push_heap (ओ (लॉग एन))