पायथन

Question

का उपयोग करके प्राथमिकता कतार में तोड़ना टाई मैं एक एल्गोरिदम लागू करने के लिए एक ढेर कतार का उपयोग कर रहा हूं, जब मैं अपनी कतार में नए नोड्स जोड़ता हूं, तो उन्हें एक ह्युरिस्टिक फ़ंक्शन द्वारा क्रमबद्ध किया जाता है: उदाहरण के लिए हेप्शश (कतार, (स्कोर (नोड)), नोड)), जो कि शानदार है, इस तथ्य के अलावा कि जब मैं कतार से अगले नोड को पॉप करने के लिए आया हूं, तो मुझे सबसे हाल ही में जोड़ा गया नोड चाहिए, जैसा कि पहले जोड़े गए नोड के विपरीत है, जो हेपॉप रिटर्न देता है। मैं इसे तोड़ने के बिना कतार में जोड़े गए सबसे हालिया नोड्स कैसे प्राप्त कर सकता हूं?

मुझे लगता है कि मैं पहले तत्व पर पुनरावृत्ति शुरू कर सकता हूं, और अगले तत्व के पास एक ही स्कोर है, जारी रखें। फिर जब मुझे उस स्कोर के साथ अंतिम तत्व मिलता है, तो मैं इसे चुनता हूं और सूची से हटा देता हूं। यह स्पष्ट रूप से बहुत ही कुशल नहीं है और प्राथमिकता कतार की समय जटिलता को तोड़ता है?

मैं इस पर अटक गया हूं और मैं इसे करने का कोई तरीका नहीं समझ सकता।

धन्यवाद।

संपादित करें; एक काउंटर का उपयोग करना, के रूप में सुझाव काम नहीं करेगा (शायद मैं गलत समझा गया है)

>>> queue = [] 
>>> heappush(queue, (2, 0, 'a')) 
>>> heappush(queue, (3, -1, 'b')) 
>>> queue 
[(2, 0, 'a'), (3, -1, 'b')] 
>>> heappush(queue, (2, -2, 'c')) 
>>> queue 
[(2, -2, 'c'), (3, -1, 'b'), (2, 0, 'a')] 

अब कतार गलत तरीके से आदेश दिया है, और 'बी' जो की तुलना में 'एक' यह पहले रखा जाता एक बुरा विकल्प नहीं है।

संपादित करें 2:

क्या हो?

>>> heappop(queue) 
(2, -2, 'c') 
>>> queue 
[(2, 0, 'a'), (3, -1, 'b')] 
>>> 

Answer 1

एक बहुत ही आसान तरीका एक मध्यम अवधि एक टाइमस्टैम्प या एक काउंटर मूल्य युक्त जोड़ना है। उदाहरण के लिए:

>>> heap = [] 
>>> counter = itertools.count() 
>>> for i in range(10): 
...  heapq.heappush(heap, (i, -next(counter), str(i) + ' oldest')) 
...  heapq.heappush(heap, (i, -next(counter), str(i) + ' newest')) 
... 
>>> heapq.heappop(heap) 
(0, -1, '0 newest') 
>>> heapq.heappop(heap) 
(0, 0, '0 oldest') 
>>> heapq.heappop(heap) 
(1, -3, '1 newest') 
>>> heapq.heappop(heap) 
(1, -2, '1 oldest') 

एजीएफ़ उल्लेख के रूप में, यह, heapq डॉक्स द्वारा प्रयोग किया जाता केवल नकारात्मक सूचकांक का उपयोग कर दृष्टिकोण है। (कार्यान्वयन में एक अच्छा कार्य हटाने और प्राथमिकता-परिवर्तन दिनचर्या भी शामिल है।)