प्राथमिकता कतार

Question

से किसी आइटम को निकालना पायथन में, heapq मॉड्यूल प्राथमिकता कतार प्रदान करता है।

इसमें आइटम डालने और पॉप करने के तरीके हैं।

आपने जो आइटम डाला है उसे हटाएं जो कतार से सबसे कम प्राथमिकता नहीं है?

(वैकल्पिक अन्य संग्रह का उपयोग कर ऐसा करने के लिए वैकल्पिक व्यंजनों स्वागत भी कर रहे हैं)

Answer 1

heapq मॉड्यूल अंतर्निहित डेटा संरचना के रूप में मानक अजगर सूचियों का उपयोग करता है, तो आप सिर्फ इस के बाद फिर से मानक list विधि remove() और heapify() उपयोग कर सकते हैं। ध्यान दें कि हालांकि इसे रैखिक समय की आवश्यकता होगी।

# Create example data and heapify 
a = range(10) 
a.reverse() 
heapq.heapify(a) 
print a 

# remove an element and heapify again 
a.remove(5) 
heapq.heapify(a) 
print a 

आप गैर-दस्तावेजी समारोह heapify._siftup() का उपयोग करके फिर से heapifying के प्रदर्शन में सुधार सकता है, लेकिन पूरी प्रक्रिया अभी भी हे (एन) list.remove() के बाद से किया जाएगा हे (एन) है।

Answer 2

एक डेटा संरचना है जिसे treap कहा जाता है जो प्राथमिकता कतार और बाइनरी पेड़ संयुक्त है। (वृक्ष की ढेर)। यह लॉग-एन खोज की अनुमति देता है जो आपकी मदद कर सकता है।

def heapq_remove(heap, index): 
    """Remove item from heap""" 

    # Move slot to be removed to top of heap 
    while index > 0: 
     up = (index + 1)/2 - 1 
     heap[index] = heap[up] 
     index = up 

    # Remove top of heap and restore heap property 
    heapq.heappop(heap) 

Answer 3

यह लॉग (एन) समारोह मेरे लिए काम करता है,

वहाँ एक Python treap implementation on PyPi .. है :

a[k] = a.pop() 
heapq.heapify(a) 

पहला कदम अब हे (1) समय है, और दूसरा गैर-दस्तावेजी डेटा का उपयोग करके बनाया जा सकता है ओ (लॉग (एन))। बेशक, यह अभी भी ओ (एन) है, यदि आपके पास पहले से नहीं है।

Answer 4

आप आइटम आप निकालना चाहते हैं के स्थान पता है, तो आप निम्न कर सकते हैं:)