बीप

एक बीप, या द्वि-अभिभावक हीप (डेटा संरचना), एक डेटा संरचना है जहां एक नोड में सामान्यतः दो माता-पिता होते हैं (जब तक कि यह एक स्तर पर प्रथम या अंतिम न हो) और दो बच्चे (जब तक कि यह अंतिम स्तर पर न हो) संग्रह के विपरीत, एक बीप सबलाइनियर या कंप्यूटर विज्ञान परिभाषा खोज की अनुमति देता है। बीप को इयान मुनरो (कंप्यूटर वैज्ञानिक) और हेंड्रा सुवांडा द्वारा प्रस्तुत किया गया था। एक संबंधित डेटा संरचना यंग दृश्य है।

बीप

प्रदर्शन

संरचना की ऊंचाई लगभग ${\sqrt {n}}$ है। साथ ही, यह मानते हुए कि अंतिम स्तर पूर्ण है, उस स्तर पर अवयव की संख्या भी ${\sqrt {n}}$ है। वास्तव में, इन गुणों के कारण सभी मूलभूत ऑपरेशन (सम्मिलित करें, हटाएं, खोजे ) औसतन $O({\sqrt {n}})$ समय में चलते हैं। सबसे व्यर्थ स्थिति में संग्रह में संचालन $O(n)$ हो सकता है। नए अवयव को हटाने और सम्मिलित करने में बीप अपरिवर्तनीय को पुनर्स्थापित करने के लिए अवयव को ऊपर या नीचे (संग्रह की तरह) फैलाना सम्मिलित है। एक अतिरिक्त लाभ यह है कि बीप अधिक छोटे अवयव तक निरंतर समय पहुंच और अधिकतम अवयव के लिए $O({\sqrt {n}})$ समय प्रदान करता है।

इसलिए, यदि प्रत्येक नोड पर पैरेंट पॉइंटर्स बनाए रखा जाता है तो एक $O({\sqrt {n}})$ फाइंड ऑपरेशन प्रयुक्त किया जा सकता है। आप शीर्ष नोड के सबसे निचले तत्व से प्रारंभ करेंगे (संग्रह में सबसे बाईं ओर के बच्चे के समान) और रुचि के तत्व को खोजने के लिए या तो ऊपर या दाएं जाएंगे।

संदर्भ

• Munro, J. Ian; Suwanda, Hendra (1980). "Implicit data structures for fast search and update". Journal of Computer and System Sciences. 21 (2): 236–250. doi:10.1016/0022-0000(80)90037-9.
• Williams, J. W. J. (Jun 1964). "Algorithm 232 - Heapsort". Communications of the ACM. 7 (6): 347–348. doi:10.1145/512274.512284.