एक PHP SplHeap वास्तव में एक ढेर है?

Question

एक हीप का PHP कार्यान्वयन वास्तव में एक पूर्ण कार्यान्वयन है?

जब मैं इस लेख को पढ़ता हूं, http://en.wikipedia.org/wiki/Heap_%28data_structure%29, मुझे यह विचार मिलता है कि एक बच्चे के नोड के पास एक विशिष्ट माता-पिता होता है, और माता-पिता के पास विशिष्ट बच्चे होते हैं।

जब मैं PHP दस्तावेज़ में उदाहरण को देखता हूं, तो http://au.php.net/manual/en/class.splheap.php, ऐसा लगता है कि बच्चे नोड्स सभी समान 'स्तर' साझा करते हैं, लेकिन विशिष्ट अभिभावक/बाल जानकारी महत्वपूर्ण नहीं है।

उदाहरण के लिए, कौन सा नोड PHP तीन उदाहरणों में से प्रत्येक तीन नोड्स के लिए अभिभावक है?

मेरे आवेदन में, जब कोई उपयोगकर्ता 'नोड 156' का चयन करता है, तो मुझे यह जानने की ज़रूरत है कि उसके बच्चे कौन हैं ताकि मैं उन्हें प्रत्येक यात्रा का भुगतान कर सकूं। (मैं उनकी पहचान 'नोड 1561', 'नोड 1562', आदि बना सकता हूं, इसलिए संबंध स्पष्ट है)।

क्या PHP हीप कार्यान्वयन अधूरा है? क्या मुझे स्प्ल क्लास को भूलना चाहिए और अपना रास्ता तय करना चाहिए? या क्या मुझे कुछ याद आ रहा है कि ढेर कैसे काम करना चाहिए? या शायद मुझे एक विशेष ढेर संस्करण को देखना चाहिए?

धन्यवाद ढेर!

Answer 1

एक हीप आमतौर पर उन प्रश्नों के उत्तर देने के लिए उपयोग किया जाता है जो "सेट में अधिकतम/न्यूनतम तत्व क्या है" के आसपास घूमते हैं।

जबकि एक ढेर संयोग से कुशलता से जवाब दे सकता है कि "अधिकतम/न्यूनतम नोड के बच्चे कौन हैं", एक ढेर उपयोग करने के लिए एक अच्छी डेटा संरचना के रूप में नहीं खड़ा होता है जब आपको अपने प्रश्न का उत्तर देने के लिए मनमाने ढंग से नोड तक पहुंचने की आवश्यकता होती है (एक नोड जो अधिकतम नोड नहीं है)। यह उपयोग करने के लिए डेटा संरचना भी नहीं है यदि विशिष्ट माता-पिता के रिश्ते हैं जिन्हें प्रतिनिधित्व और रखरखाव करने की आवश्यकता है, क्योंकि बच्चे विभिन्न माता-पिता नोड्स के बीच स्वैप कर सकते हैं और कर सकते हैं।

तो php का ढेर कार्यान्वयन निश्चित रूप से इन आधारों पर अपूर्ण नहीं है। आपको बस एक अलग डेटा संरचना की आवश्यकता है।

Answer 2

इस ढेर कार्यान्वयन के लिए एपीआई सरणी पहुंच की अनुमति नहीं देता है, जो आपको इस मामले में चाहिए। ढेर आमतौर पर अन्य संरचनाओं को लागू करने के लिए उपयोग किए जाते हैं जो आपको शीर्ष से वस्तुओं को आसानी से हटाने की अनुमति देते हैं।

आप एक रैपर इटरेटर बना सकते हैं जो आपको आवश्यक पदों की तलाश करता है। मुझे संदेह है कि यह एक खराब प्रदर्शन समाधान होगा और बहुत अच्छा नहीं होगा।

---

इस स्थिति में, BinaryTree मुझे लगता है कि आपको क्या चाहिए। पेड़ में एक जगह को देखते हुए आप अपने बच्चों को नीचे जा सकते हैं क्योंकि वे सीधे जुड़े हुए हैं। मेरे पास BinarySearchTree है जो पेड़ का आदेश रखेगा और BinaryTree की एक प्रति प्राप्त करने के लिए आप getRoot पर कॉल कर सकते हैं। एक AvlTree भी है जो पेड़ को इष्टतम खोज के लिए संतुलित रखेगा।