ओ (लॉगन) समय में एसटीएल ढेर के साथ कम करने की कुंजी लागू करना

Question

इस समय एसटीएल हीप कम करने की कुंजी का समर्थन नहीं करता है, हालांकि कोई भी सीधे वेक्टर पर मूल्य बदल सकता है और फिर मेक_हेप को कॉल कर सकता है जो ओ (एन) समय है। हालांकि यह एक बाइनरी ढेर कम करने की कुंजी के रूप में उतना कुशल नहीं है जो ओ (लॉगन) समय लेगा।

क्या एसटीएल ढेर कार्यों का उपयोग कर ओ (लॉगन) समय प्राप्त करने का कोई तरीका है?

Answer 1

आप pop_heap मूल्य push_heap के बाद decrementing के बाद का उपयोग कर सकते हैं:

int main() { 
    //Create the heap 
    std::vector<int> heap{1,2,3,4,5,6,7}; 
    std::make_heap(heap.begin(), heap.end()); 

    //Decrease key 
    std::pop_heap(heap.begin(), heap.end()); 
    --*(std::prev(heap.end())); 
    std::push_heap(heap.begin(), heap.end()); 
} 

संपादित करें: क्या यह तुम क्या मतलब है, या आप में किसी भी तत्व की कुंजी कम करने के लिए सक्षम होने के लिए चाहते हो ढेर?

वहाँ कम किए/वृद्धि कुंजी आपरेशन

यह जाता है हालांकि कोई मानक समर्थन है: Wikipedia says so too -

Answer 2

मैं बहुत यकीन है कि वहाँ यह करने का कोई मानक-अनुरूप रास्ता है कर रहा हूँ gheap लाइब्रेरी को इंगित करने के लिए, जो कि एक नज़र के लायक हो सकता है।

समस्या यह है कि मानदंड यह नहीं है कि ढेर संरचना किस प्रकार होती है, न ही संचालन कैसे किया जाता है। तो मुझे लगता है कि आप बस heap[i] पर तत्व कम कर सकते हैं और फिर push_heap(heap.begin(), heap.begin() + i + 1) है, जो आवश्यक ऊपर ढेर आपरेशन करना होगा फोन कार्यान्वयन एक मानक द्विआधारी ढेर उपयोग कर रहा है (सामान्य तौर पर यह एक अच्छी बात है।)

। तत्व i पर समाप्त होने वाला तत्व मूल रूप से मूल्य से बड़ा नहीं होना चाहिए, और इसलिए पूरे ढेर की ढेर संपत्ति संरक्षित है। लेकिन यह मानक द्वारा समर्थित नहीं है भले ही यह कभी-कभी कुछ कार्यान्वयन में काम करता है।