द्विआधारी ढेर में हटाना

Question

मैं बस बाइनरी ढेर सीखने की कोशिश कर रहा हूं और बाइनरी ढेर में हटाने के संचालन के बारे में संदेह है। मैंने पढ़ा है कि हम बाइनरी ढेर से एक तत्व हटा सकते हैं और हमें इसे फिर से हासिल करने की आवश्यकता है।

लेकिन दिए गए लिंक पर, यह अनुपलब्ध कहते हैं:

http://en.wikibooks.org/wiki/Data_Structures/Tradeoffs

   Binary Search AVL Tree Binary Heap (min) Binomial Queue (min) 

Find   O(log n)  O(log n) unavailable   unavailable 
Delete element O(log n  O(log n) unavailable   unavailable 

मैं थोड़ा इसके बारे में उलझन में हूँ।

सभी स्पष्टीकरणों के लिए अग्रिम धन्यवाद।

Answer 1

बाइनरी ढेर और अन्य प्राथमिकता कतार संरचना आमतौर पर एक सामान्य "तत्व हटाएं" ऑपरेशन का समर्थन नहीं करते हैं; आपको एक अतिरिक्त डेटा संरचना की आवश्यकता है जो ढेर में प्रत्येक तत्व की अनुक्रमणिका का ट्रैक रखती है, उदा। एक हैश टेबल आपको लगता है कि है, तो आप कम से कम से कम करने के लिए

• ढूंढें तत्व हे एक हैश तालिका
• decrease key साथ (1) समय की उम्मीद के रूप में एक सामान्य हटाने आपरेशन लागू कर सकते हैं, हे (एलजी n) समय
• हटाएं-मिनट और हैश तालिका अपडेट करें, ओ (एलजी एन) संयुक्त अपेक्षित समय।

Answer 2

एक नियमित हटाने सिर्फ एक DeleteMin/अधिकतम तरह संभव है। "समस्या" यह है कि आपको ऊपर और डाउनशिप दोनों की जांच करनी है (यानी: जब "अंतिम" नोड रिक्त स्थान लेता है, तो यह अधिक या अवांछित हो सकता है। चूंकि यह अभी भी दोनों के लिए स्पष्ट नहीं हो सकता है कारणों से, यह शुद्धता के लिए जाँच करने के लिए आसान है।

केवल समस्या यह है कि लगता है। जवाब राज्यों के ऊपर है कि आप हे में तत्व का पता लगाएं कर सकते हैं (एलजी एन) रहता है, लेकिन मैं कैसे पता नहीं होता। मेरे प्रयोगों में, मैं आम तौर पर तत्वों के बजाय पॉइंटर्स-टू-एलिमेंट्स का एक ढेर बनाता हूं (अप/डाउनशिप के दौरान सस्ता प्रतिलिपि)। मैं एलिमेंट प्रकार में "स्थिति" चर जोड़ता हूं, जो हीप में एलिमेंट के पॉइंटर के सूचकांक का ट्रैक रखता है। एक तत्व ई दिया गया, मैं स्थिर समय में हीप में इसकी स्थिति पा सकता हूं।

जाहिर है, यह हर लागू करने के लिए कट नहीं है प्रलेखन।

Answer 3

मुझे उलझन में है कि बाइनरी ढेर के ऑपरेशन को हटाएं क्यों आपके प्रश्न के लिंक में अनुपलब्ध है। द्विआधारी ढेर में काफी हद तक हटाना और यह बाइनरी ढेर के 2 अन्य परिचालनों की संरचना है। https://en.wikipedia.org/wiki/Binary_heap

मैं विचार कर रहा हूँ आप को हटाया जा रहा द्विआधारी ढेर से एक महत्वपूर्ण कोड/आपरेशन के 2 लाइनों की आवश्यकता है द्विआधारी ढेर

के सभी अन्य कार्यों में पता है। मान लीजिए कि आप इंडेक्स x पर आइटम हटाना चाहते हैं। इसके मूल्य को सबसे कम पूर्णांक के लिए घटाएं। वह Integer.MIN_VALUE है। चूंकि यह सभी पूर्णांक का सबसे कम मूल्य है, इसलिए decreaseItem(int index, int newVal) निष्पादन पूर्ण होने पर यह रूट स्थिति पर जायेगा। बाद में extractMin() विधि का उपयोग करने वाले रूट को निकालें।

// Complexity: O(lg n) 
public void deleteItem(int index) { 
    // Assign lowest value possible so that it will reach to root 
    decreaseItem(index, Integer.MIN_VALUE); 
    // Then extract min will remove that item from heap tree. correct ? 
    extractMin(); 
} 

पूर्ण कोड: BinaryHeap_Demo.java