मिनी-हीप आधारित प्राथमिकता कतार के लिए ओ (लॉगन) कमी-कुंजी ऑपरेशन को कैसे कार्यान्वित करें?

Question

मैं एक ऐसे अनुप्रयोग पर काम कर रहा हूं जो Djikstra के एल्गोरिदम को प्रदर्शित करता है, और इसका उपयोग करने के लिए, मुझे अपने तत्वों के मूल्य में कमी होने पर ढेर संपत्ति को पुनर्स्थापित करने की आवश्यकता है।

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

इसके अलावा, मैं ऑपरेशन के लिए आवश्यक वास्तविक कोड के बारे में बिल्कुल निश्चित नहीं हूं। मैं अपनी प्राथमिकता कतार के लिए डी-हीप here का उपयोग कर रहा हूं। स्यूडोकोड मदद करेगा, लेकिन जावा में एक उदाहरण पसंद करेंगे कि यह कैसे किया जाना चाहिए।

Answer 1

आप निम्न कार्य कर सकते हैं: अपने ढेर के अंदर एक हैशपैप स्टोर करें जो आपके ढेर मूल्य इंडेक्स को ढेर करने के लिए मानचित्र करता है। तो फिर आप अपने सामान्य ढेर-तर्क का विस्तार करना चाहिए सिर्फ एक सा:

on Swap(i, j): 
    map[value[i]] = j; 
    map[value[j]] = i; 

---

on Insert(key, value): 
    map.Add(value, heapSize) in the beginning; 

---

on ExtractMin: 
    map.Remove(extractedValue) in the end; 

---

on UpdateKey(value, newKey): 
    index = map[value]; 
    keys[index] = newKey; 

BubbleUp(index)DecreaseKey के मामले में, और BubbleDown/Heapify(index)IncreaseKey के मामले में , मिनी-हीप-प्रोपे को बहाल करने के लिए rty। http://pastebin.com/kkZn123m

सम्मिलित और ExtractMin कॉल स्वैप लॉग (एन) के समय, जब बहाल ढेर संपत्ति:

यहाँ मेरी सी # कार्यान्वयन है। और आप स्वैप करने के लिए ओ (1) ओवरहेड जोड़ रहे हैं, इसलिए दोनों ऑपरेशन ओ रहे हैं (लॉग (एन))। UpdateKey भी लॉग (एन) है: पहले आप ओ (1) के लिए हैशैप में इंडेक्स को लुकअप करते हैं, फिर आप ओ (लॉग (एन)) के लिए हीप प्रॉपर्टी को पुनर्स्थापित कर रहे हैं जैसा कि आप Insert/ExtractMin में करते हैं।

महत्वपूर्ण नोट: इंडेक्स लुकअप के लिए मूल्यों का उपयोग करने के लिए आवश्यक है कि वे अद्वितीय हैं। यदि आप इस स्थिति के साथ ठीक नहीं हैं, तो आपको अपने कुंजी-मूल्य जोड़े में कुछ अद्वितीय आईडी जोड़नी होगी और मूल्य-अनुक्रमणिका मैपिंग के बजाय इस अद्वितीय आईडी और ढेर इंडेक्स के बीच मैपिंग बनाए रखना होगा। लेकिन डिजस्ट्रा के लिए इसकी आवश्यकता नहीं है, क्योंकि आपके मान ग्राफ़ नोड्स होंगे और आप अपनी प्राथमिकता कतार में डुप्लिकेट नोड्स नहीं चाहते हैं।

Answer 2

प्रति this SO question डिजस्ट्रा के एल्गोरिदम को लागू करने के लिए कमी-कुंजी विधि होने के लिए अनावश्यक है।

आप जितनी बार आवश्यक हो उतनी बार प्राथमिकता कतार में एक आइटम जोड़ सकते हैं और डुप्लिकेट को बाहर निकालने के लिए आपके द्वारा देखे जाने वाले नोड्स का ट्रैक रखें। पहली बार जब आप कतार से इसे पॉप करके एक नोड पर जाते हैं, तो आपको उस नोड का सबसे छोटा रास्ता मिल गया है और प्राथमिकता कतार पर इसकी सभी भविष्य की घटनाओं को अनदेखा कर सकता है।

प्राथमिकता कतार पर कई अतिरिक्त नोड्स होने से समस्या बहुत अधिक नहीं है क्योंकि यह O(log N) संरचना है। (आपको 1 मिलियन वस्तुओं के लिए 20 तुलना और 1 अरब वस्तुओं के लिए 30 तुलना करना है।)

संपादित करें: बाद में इस सवाल पर के बाद, मैं थोड़ा मेरा उत्तर से निराश हूं: उन चीजों के सभी कतार के बाहर आ गया है जब तक आप कुछ विशेष canipulations बाद में करना होगा। जीवन में कई चीजों की तरह, यह नीचे आता है कि आप अपनी याददाश्त और ऐसा करने से जुड़े लागतों का प्रबंधन कैसे करते हैं। लेकिन सामान्य बिंदु बनी हुई है: कमी-कुंजी आवश्यक है, भले ही यह वांछनीय हो।

Answer 3

यदि आप C++ stl make_heap()/pop_heap()/push_heap() का उपयोग कर रहे हैं, तो अंडरलाइन हेप वेक्टर में इंडेक्स से इंडेक्स में इंडेक्स रखने के लिए कोई तरीका नहीं है, मुझे लगता है कि आपको अपने हीप फ़ंक्शन को लागू करना चाहिए बढ़ने-कुंजी/घटाने-कुंजी ऑपरेशन में ओ (लॉगऑन) प्राप्त करने के लिए।