एक std :: heap

Question

के बीच से एक तत्व निकालें मैं एक अतिरिक्त आवश्यकता के साथ शेड्यूलर के रूप में प्राथमिकता कतार का उपयोग कर रहा हूं। मुझे अनुसूचित वस्तुओं को रद्द करने में सक्षम होना चाहिए। यह प्राथमिकता कतार के बीच से किसी आइटम को हटाने के बराबर है।

मैं std::priority_queue का उपयोग शीर्ष के अलावा किसी अन्य तत्व तक पहुंच के रूप में नहीं कर सकता।

मैं algorithm के ढेर कार्यों का उपयोग करने की कोशिश कर रहा हूं। लेकिन मुझे अभी भी उस टुकड़े को याद आ रहा है जो मुझे चाहिए। जब मैं ढेर के बीच से एक तत्व हटा देता हूं, तो मैं इसे कुशलता से पुनर्निर्माण करना चाहता हूं।

• std::make_heapओ (3n)
• std::push_heapओ (एलजी (एन))
• std::pop_heapहे (2 एलजी (एन))

: सी ++ इन ढेर कार्य प्रदान

मुझे एक नया फ़ंक्शन चाहिए जैसे std::repair_heap एक बड़े-ओ < 3n। मैं इसे छेद के स्थान के साथ प्रदान करूंगा जहां रद्द आइटम का उपयोग किया जाता था और यह ठीक से ढेर को समायोजित करेगा।

यह std::repair_heap फ़ंक्शन प्रदान नहीं करने के लिए एक बड़ी निगरानी प्रतीत होता है। क्या मुझसे साफ़ - साफ़ कुछ चीज़ चूक रही है?

क्या ऐसी लाइब्रेरी है जो एक stl-compliant std::repair_heap प्रदान करती है?

क्या शेड्यूलर मॉडलिंग के लिए कोई बेहतर डेटा संरचना है?

नोट:
मैं कुछ कारणों के लिए एक std::map का उपयोग नहीं कर रहा हूँ।

• एक ढेर में लगातार स्मृति ओवरहेड है।
• एक ढेर में शानदार कैश इलाके है।

Answer 1

दुर्भाग्यवश, मानक इस (काफी महत्वपूर्ण) फ़ंक्शन को याद कर रहा है। जी ++ के साथ, आप ऐसा करने के लिए गैर-मानक फ़ंक्शन std::__adjust_heap का उपयोग कर सकते हैं, लेकिन ऐसा करने का कोई आसान पोर्टेबल तरीका नहीं है - और __adjust_heap g ++ के विभिन्न संस्करणों में थोड़ा अलग है, इसलिए आप इसे g ++ संस्करणों पर पोर्टेबल रूप से भी नहीं कर सकते ।

Answer 2

ऐसा नहीं है कि एक ढेर के बीच से हटाने के पूरे ढेर मतलब हो सकता है मुझे लगता है फिर से बनाया जाना है: कारण कोई repair_heap है है, क्योंकि यह भी ऐसा ही करने (बड़ा, ओह) make_heap के रूप में काम करना होगा ।

क्या आप ढेर में std::pair<bool, Item> डालकर कुछ ऐसा करने में सक्षम हैं और केवल उन्हें हटाने के बजाय आइटम को अमान्य कर सकते हैं? फिर जब वे आखिरकार शीर्ष पर पहुंच जाते हैं तो आइटम को अनदेखा करते हैं और आगे बढ़ते हैं।

Answer 3

आपके repair_heap() कैसे काम करता है? मेरा अनुमान है:

यदि आपका ढेर कुछ इटरेटर रेंज द्वारा परिभाषित किया गया है, तो कहें (हेपबेजिन, हेपएंड)। जिस तत्व को आप निकालना चाहते हैं वह ढेर के कुछ उप-भाग की जड़ है, जिसे कुछ सब्रेंज (सबहेपबिन, सबहेपेंड) द्वारा परिभाषित किया जाता है।std::pop_heap(subHeapBegin, subHeapEnd) का उपयोग करें, फिर subHeapEnd != heapEnd, मानों को *(subHeapEnd-1) और *(heapEnd-1) पर स्वैप करें, जो आपके हटाए गए आइटम को ढेर कंटेनर के अंत में रखना चाहिए। अब आपको अपने उपशीर्षक में * (subHeapEnd-1) पर तत्व को प्रतिबिंबित करना होगा। अगर मुझे कुछ याद नहीं आया है, जो संभव है, तो वह सब कुछ है जो ढेर कंटेनर के अंत तत्व को काटना है।

सही ढंग से कोड करने की कोशिश करने की परेशानी पर जाने से पहले (मैंने कुछ विवरण छोड़ दिए हैं जैसे सबहेपबिन और सबहेपेंड), मैं यह निर्धारित करने के लिए कुछ परीक्षण चलाऊंगा कि make_heap() वास्तव में आपको धीमा कर देता है या नहीं। बिग-ओ उपयोगी है, लेकिन यह वास्तविक निष्पादन समय के समान नहीं है।

Answer 4

यहां एक छोटा सा डेल्फी कोड है जिसका उपयोग मैं एक ढेर से वस्तुओं को हटाने के लिए करता था। मैं इस सी ++, जिनमें से आप बोलते हैं और एक की मरम्मत समारोह की जरूरत नहीं है

पहले पॉप पता नहीं है, लेकिन हे .., तो आप बात कैसे काम करता है की एक विचार प्राप्त:

function THeap.Pop: HeapItem; 
begin 
    if fNextIndex > 1 then begin 
    Dec(fNextIndex); 
    Result:= fBuckets[1]; //no zero element 
    fBuckets[1] := fBuckets[fNextIndex]; 
    fBuckets[fNextIndex] := nil; 
    FixHeapDown;   //this has a param defaulting to 
    end 
    else 
    Result:= nil; 
end; 

अब विपरीत, विलोपन:

procedure THeap.Delete(Item: HeapItem); 
var 
    i:integer; 
begin 
    for i:=1 to pred(fNextIndex) do 
    if Item=fBuckets[i] then begin 
     dec(fNextIndex); 
     fBuckets[i] := fBuckets[fNextIndex]; 
     fBuckets[fNextIndex] := nil; 
     FixHeapDown(i); 
     break; 
     end; 
end; 

इसकी निश्चित रूप से नहीं-नहीं भी सोचने के लिए के बारे में कर हम यहाँ क्या कर रहे हैं, लेकिन हे, लागत और नौकरियों कभी कभी बदल सकता हूँ रद्द मिलता है।

आनंद लें। मुझे उम्मीद है कि यह मदद करता है।

Answer 5

मुझे लगता है कि आप जानते हैं कि ढेर कंटेनर (इंडेक्स एन) में कौन सा तत्व आप हटाना चाहते हैं।

1. मूल्य v[n] = BIG; मूल्य BIG ढेर में किसी भी अन्य मूल्यों से वास्तव में बड़ा है निर्धारित करें।
2. कॉल std::push_heap(v.begin(), v.begin()+n+1);
3. कॉल std::pop_heap(v.begin(), v.end());
4. कॉल v.pop_back();
5. हो गया

ऑपरेशन हे है (ln (एन))

उत्तर: सबूत के लिए अनुरोध

सबसे पहले, एक क्वालीफायर: यह विधि अल के बारे में कुछ मानती है gorithm std push_heap द्वारा उपयोग किया जाता है।
विशेष रूप से, यह मानता है कि std push_heap (v.begin(), v.begin() + n + 1) केवल उन तत्वों के लिए श्रेणी [0, n]
को बदल देगा जो एन के आरोही हैं, यानी, निम्नलिखित सेट में सूचकांक:

http://www.cplusplus.com/reference/algorithm/push_heap/ "एक ढेर रेंज [देखते हुए पहले, पिछले -1), इस समारोह श्रृंखला के लिए एक ढेर माना लागू होता है:

A(n)={n,(n-1)/2,((n-1)/2-1)/2....0}. 

यहाँ एसटीडी push_heap के लिए एक विशिष्ट कल्पना है [पहले, आखिरी) मूल्य को (अंतिम -1) में इसके संबंधित स्थान में रखकर। "

क्या यह पाठ्यपुस्तकों में पढ़ने वाले "सामान्य ढेर एल्गोरिदम" का उपयोग करने की गारंटी देता है? आप मुझे बताओ।

वैसे भी, यह कोड है जिसे आप चला सकते हैं और देख सकते हैं, अनुभवजन्य रूप से, यह काम करता है। मैं कुलपति 2005.

#include <algorithm> 
#include <vector> 
#include <iostream> 

bool is_heap_valid(const std::vector<int> &vin) 
{ 
    std::vector<int> v = vin; 
    std::make_heap(v.begin(), v.end()); 
    return std::equal(vin.begin(), vin.end(), v.begin()); 
} 


int _tmain(int argc, _TCHAR* argv[]) 
{ 
    srand(0); 
    std::vector<int> v; 
    for (int i=0; i<100; i++) 
    { 
     v.push_back(rand() % 0x7fff); 
    } 
    std::make_heap(v.begin(), v.end()); 

    bool bfail = false; 
    while(v.size() >= 2) 
    { 
     int n = v.size()/2; 
     v[n] = 0x7fffffff; 
     std::push_heap(v.begin(), v.begin()+n+1); 
     std::pop_heap(v.begin(), v.end()); 
     v.resize(v.size()-1); 
     if (!is_heap_valid(v)) 
     { 
      std::cout << "heap is not valid" << std::endl; 
      bfail = true; 
      break; 
     } 
    } 
    if (!bfail) 
     std::cout << "success" << std::endl; 

    return 0; 

} 

उपयोग कर रहा हूँ लेकिन मैं एक और समस्या है, जो पता है कि कैसे सूचकांक "n" जो हटाना आवश्यक है है। मैं नहीं देख सकता कि std push_heap और std pop_heap का उपयोग करते समय इसका ट्रैक कैसे रखें (ढेर में जगह जानें)। मुझे लगता है कि आपको अपना हीप कोड लिखना होगा और ऑब्जेक्ट को ढेर में स्थानांतरित होने पर ऑब्जेक्ट को ढेर में इंडेक्स लिखना होगा। आह।