बीप

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

बीप

प्रदर्शन

संरचना की ऊंचाई लगभग है ${\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.