पायथन: ढेर से तत्व हटाएं

Question

पायथन में heapq मॉड्यूल है जो ढेर डेटा संरचना लागू करता है और यह कुछ बुनियादी संचालन (पुश, पॉप) का समर्थन करता है।

ओ (लॉग एन) में ढेर से i-th तत्व को कैसे निकालें? क्या यह heapq के साथ भी संभव है या क्या मुझे एक और मॉड्यूल का उपयोग करना है? - यह नहीं है जो मैं चाहता http://docs.python.org/library/heapq.html जो एक संभव दृष्टिकोण का सुझाव:

ध्यान दें, वहाँ प्रलेखन के तल पर एक उदाहरण है। मैं तत्व को हटाना चाहता हूं, न केवल हटाए जाने के रूप में चिह्नित करें।

Answer 1

आप काफी आसानी से एक ढेर से आई-वें तत्व निकाल सकते हैं:

h[i] = h[-1] 
h.pop() 
heapq.heapify(h) 

बस तत्व आप पिछले तत्व के साथ हटाने और ढेर फिर से heapify तो पिछले तत्व निकालना चाहते बदलें। यह ओ (एन) है, यदि आप चाहते हैं कि आप ओ (लॉग (एन)) में एक ही काम कर सकें, लेकिन आपको कुछ आंतरिक हेपफाइफ़ फ़ंक्शंस को कॉल करने की आवश्यकता होगी, या बेहतर होगा क्योंकि लार्सन ने इंगित किया है कि बस स्रोत को कॉपी करें _siftup/अपने खुद के कोड में heapq.py से बाहर _siftdown:

h[i] = h[-1] 
h.pop() 
if i < len(h): 
    heapq._siftup(h, i) 
    heapq._siftdown(h, 0, i) 

ध्यान दें कि प्रत्येक मामले में तुम बस ऐसा नहीं कर सकते h[i] = h.pop() कि मानो i संदर्भ पिछले तत्व विफल हो जाएगा। यदि आप अंतिम तत्व को हटाते हुए विशेष मामला तो आप ओवरराइट और पॉप को जोड़ सकते हैं।

नोट अपने ढेर के विशिष्ट आकार के आधार पर आपको पता चल सकता है कि कि बस बुला heapify जबकि सैद्धांतिक रूप से कम कुशल _siftup/_siftdown फिर से उपयोग करने की तुलना में तेजी से हो सकता है: आत्मनिरीक्षण का एक छोटा सा पता चलता है कि heapify शायद सी में कार्यान्वित किया जाता है लेकिन आंतरिक कार्यों के सी कार्यान्वयन का खुलासा नहीं किया गया है। यदि प्रदर्शन आपके लिए महत्वपूर्ण है तो सामान्य डेटा पर कुछ समय परीक्षण करने पर विचार करें कि यह सर्वोत्तम है। जब तक कि आप वास्तव में बड़े पैमाने पर ढेर नहीं करते हैं-ओ शायद सबसे महत्वपूर्ण कारक नहीं हो सकता है।

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

_siftdown की जरूरत नहीं है: कोई व्यक्ति कोई टिप्पणी उस के साथ _siftdown का कॉल निकालना इस जवाब को संपादित करने की कोशिश की। नया एच [i] पुराना एच [i] के बच्चों में से सबसे छोटा होने की गारंटी है, जो अभी भी पुराने एच [i] के माता-पिता (नया एच [i] के माता-पिता) से बड़ा है। _siftdown एक नो-ओप होगा। मुझे संपादित करना है क्योंकि मैं में अभी तक कोई टिप्पणी जोड़ने के लिए पर्याप्त प्रतिनिधि नहीं है।

क्या वे इस टिप्पणी में नहीं छूटा है कि h[-1]h[i] का एक बच्चा बिल्कुल नहीं हो सकता है। h[i] पर डाला गया नया मान ढेर की पूरी तरह से अलग शाखा से आ सकता है, इसलिए इसे किसी भी दिशा में विभाजित करने की आवश्यकता हो सकती है।

टिप्पणी क्यों सिर्फ ढेर बहाल करने के लिए sort() का उपयोग नहीं पूछ करने के लिए

इसके अलावा: _siftup और _siftdown बुला दोनों हे आपरेशन (एन लॉग इन करें), heapify बुला रहे हैं हे (एन) है।कॉलिंग sort() एक ओ (एन लॉग एन) ऑपरेशन है। यह काफी संभव है कि कॉलिंग सॉर्ट पर्याप्त तेज़ होगा लेकिन बड़े ढेर के लिए यह एक अनावश्यक ओवरहेड है।

संपादित @Seth Bruder द्वारा जारी किए गए मुद्दे से बचने के लिए। जब i अंतिम तत्व का संदर्भ देता है _siftup() कॉल विफल हो जाएगा, लेकिन उस स्थिति में ढेर के अंत से एक तत्व पॉपिंग ढेर परिवर्तक को तोड़ नहीं देता है।

Answer 2

(ए) विचार करें कि आप आलसी हटाना क्यों नहीं चाहते हैं। यह कई मामलों में सही समाधान है।

(बी) एक ढेर एक सूची है। आप किसी भी अन्य सूची की तरह इंडेक्स द्वारा एक तत्व को हटा सकते हैं, लेकिन फिर आपको इसे फिर से अनुकूलित करने की आवश्यकता होगी, क्योंकि यह अब ढेर इनवेरिएंट को संतुष्ट नहीं करेगा।